Determining a cycle basis of a directed graph
US7913209B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 13, 2008 |
| Grant date | Mar 22, 2011 |
| Priority date | — |
| Expiry date | Jul 12, 2029 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F30/30
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A cycle basis is efficiently determined for a directed graph. A first depth-first search of the directed graph classifies each of the edges of the directed graph to have a type that is one of a within-tree type for an edge within a tree of the first depth first search, a forward type for an edge skipping forward along the tree, a back type for an edge directed back along the tree, or a cross type for an edge between two subtrees of the tree. A second depth-first search of the directed graph determines a respective cycle for each of the edges of the back type. A third depth-first search of the directed graph determines a respective cycle for each of the edges of the cross type that is included a cycle. The basis is output the basis that specifies each of the respective cycles.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.