Name
Abstract | ||
|---|---|---|
We consider the problem of detecting a cycle in a directed graph that grows by arc insertions and the related problems of maintaining a topological order and the strong components of such a graph. For these problems, we give two algorithms, one suited to sparse graphs, the other to dense graphs. The former takes O(min {m1/2, n2/3}m) time to insert m arcs into an n-vertex graph; the latter takes O(n2log n) time. Our sparse algorithm is substantially simpler than a previous O(m3/2)-time algorithm; it is also faster on graphs of sufficient density. The time bound of our dense algorithm beats the previously best time bound of O(n5/2) for dense graphs. Our algorithms rely for their efficiency on vertex numberings weakly consistent with topological order: we allow ties. Bounds on the size of the numbers give bounds on running time. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/2756553 | ACM Transactions on Algorithms (TALG) |
Keywords | Field | DocType |
Algorithms,Theory,Topological ordering,cycle detection,strongly connected components,incremental data structure | Discrete mathematics,Indifference graph,Combinatorics,Chordal graph,Cycle graph,Hopcroft–Karp algorithm,Pathwidth,1-planar graph,Topological graph theory,Mathematics,Dense graph | Journal |
Volume | Issue | ISSN |
abs/1112.0784 | 2 | 1549-6325 |
Citations | PageRank | References |
12 | 0.68 | 26 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael A. Bender | 1 | 2144 | 138.24 |
| Jeremy T. Fineman | 2 | 587 | 36.10 |
| Seth Gilbert | 3 | 1413 | 94.72 |
| Robert Endre Tarjan | 4 | 25160 | 6384.61 |