TY - GEN

T1 - Incremental topological sort and cycle detection in Õ (m √n) expected total time

AU - Bernstein, Aaron

AU - Chechik, Shiri

N1 - Publisher Copyright:
© Copyright 2018 by SIAM.

PY - 2018

Y1 - 2018

N2 - In the incremental cycle detection problem edges are inserted to a directed graph (initially empty) and the algorithm has to report once a directed cycle is formed in the graph. A closely related problem to the incremental cycle detection is that of the incremental topological sort problem, in which edges are inserted to an acyclic graph and the algorithm has to maintain a valid topological sort on the vertices at all times. Both incremental cycle detection and incremental topological sort have a long history. The state of the art is a recent breakthrough of Bender, Fineman, Gilbert and Tarjan [TALG 2016], with two different algorithms with respective total update times of Õ (n2) and O(m minfm1=2; n2=3g). The two algorithms work for both incremental cycle detection and incremental topological sort. In this paper we introduce a novel technique that allows us to improve upon the state of the art for a wide range of graph sparsity. Our algorithms has a total expected update time of Õ(m p n) for both the incremental cycle detection and the topological sort problems.

AB - In the incremental cycle detection problem edges are inserted to a directed graph (initially empty) and the algorithm has to report once a directed cycle is formed in the graph. A closely related problem to the incremental cycle detection is that of the incremental topological sort problem, in which edges are inserted to an acyclic graph and the algorithm has to maintain a valid topological sort on the vertices at all times. Both incremental cycle detection and incremental topological sort have a long history. The state of the art is a recent breakthrough of Bender, Fineman, Gilbert and Tarjan [TALG 2016], with two different algorithms with respective total update times of Õ (n2) and O(m minfm1=2; n2=3g). The two algorithms work for both incremental cycle detection and incremental topological sort. In this paper we introduce a novel technique that allows us to improve upon the state of the art for a wide range of graph sparsity. Our algorithms has a total expected update time of Õ(m p n) for both the incremental cycle detection and the topological sort problems.

UR - http://www.scopus.com/inward/record.url?scp=85045543349&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85045543349&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975031.2

DO - 10.1137/1.9781611975031.2

M3 - Conference contribution

AN - SCOPUS:85045543349

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 21

EP - 34

BT - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

A2 - Czumaj, Artur

PB - Association for Computing Machinery

T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

Y2 - 7 January 2018 through 10 January 2018

ER -