A new approach to incremental cycle detection and related problems

Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Robert E. Tarjan

Research output: Contribution to journalArticle

12 Scopus citations

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(n2 log 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.

Original languageEnglish (US)
Article number14
JournalACM Transactions on Algorithms
Volume12
Issue number2
DOIs
StatePublished - Dec 1 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics (miscellaneous)

Keywords

  • Cycle detection
  • Incremental data structure
  • Strongly connected components
  • Topological ordering

Fingerprint Dive into the research topics of 'A new approach to incremental cycle detection and related problems'. Together they form a unique fingerprint.

  • Cite this