Determining a cycle basis of a directed graph

Details Determining a cycle basis of a directed graph Determining a cycle basis of a directed graph

2011-03-22

2011-03-22

Kik, Phallaka (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Integrated circuit design processing

Logic design processing

C716S105000, C716S136000, C703S014000, C703S002000, C707S708000, C707S797000, C707S798000

Reexamination Certificate

active

07913209

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.

REFERENCES:
patent: 5522063 (1996-05-01), Ashar et al.
patent: 5889999 (1999-03-01), Breternitz et al.
patent: 6282681 (2001-08-01), Sun et al.
patent: 6381739 (2002-04-01), Breternitz et al.
patent: 6804634 (2004-10-01), Holzmann et al.
patent: 6879946 (2005-04-01), Rong et al.
patent: 7693690 (2010-04-01), Wang et al.
patent: 2007/0044084 (2007-02-01), Wang et al.
patent: 2009/0222249 (2009-09-01), Wang et al.
Liu, Hongbo et al., “A New Way To Enumerate Cycles in Graph”, Telecommunications, 2006 AICT-ICIW apos; 06. International Conference on Internet and Web Applications and Services, Feb. 19-26, 2006, 3 pages.
Liebchen, Christian, et al., “A Greedy Approach To Compute A Minimum Cycle Basis Of A Directed Graph”, Inf. Process. Lett 94(3): 107-112 Jan. 20, 2005, 17 pages.
Tarjan, R. “Enumeration Of The Elementary Circuits Of A Directed Graph”, Department of Computer Science, Cornell University, TR 72-145, Sep. 1972, 15 pages.
Johnson, D.B., “Find All The Elementary Circuits Of A Directed Graph”, J.Siam, 4:77-84, 1975, http://scitation.aip.org, (Abstract).

Affiliated with

Also associated with

Rating

Determining a cycle basis of a directed graph does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Determining a cycle basis of a directed graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Determining a cycle basis of a directed graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2653149