Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance

DOI10.1145/2071379.2071382zbMath1295.05234arXiv1105.2397OpenAlexW2055688322MaRDI QIDQ3189043

Telikepalli Kavitha, Bernhard Haeupler, Rogers Mathew, Siddhartha Sen, Robert Endre Tarjan

Publication date: 9 September 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1105.2397

zbMATH Keywords

directed graphsdynamic algorithmsarrangementtopological orderstrong componentscycle detectionhalving intersection

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Online algorithms; streaming algorithms (68W27)

Related Items (10)

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ A multi-threading algorithm to detect and remove cycles in vertex- and arc-weighted digraph ⋮ Strategies for ensuring required service level for COVID-19 herd immunity in Indian vaccine supply chain ⋮ Accelerating the calculation of makespan used in scheduling improvement heuristics ⋮ Approximations of the Lagrange and Markov spectra ⋮ Topological sorts on DAGs ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time ⋮ Structure learning of Bayesian networks using global optimization with applications in data classification

This page was built for publication: Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance