The Library
An improved algorithm for incremental cycle detection and topological ordering in sparse graphs
Tools
Tools
Tools
Bhattacharya, Sayan and Kulkarni, Janardhan (2020) An improved algorithm for incremental cycle detection and topological ordering in sparse graphs. In: 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Salt Lake City, Utah, U.S., 5-8 Jan 2020. Published in: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2509-2521 . ISBN 9781611975994. doi:10.1137/1.9781611975994.153
|
PDF
WRAP-improved-algorithm-incremental-cycle-detection-topological-ordering-sparse-graphs-Bhattacharya-2020.pdf - Accepted Version - Requires a PDF viewer. Download (914Kb) | Preview |
Official URL: https://doi.org/10.1137/1.9781611975994.153
Abstract
We consider the problem of incremental cycle detection and topological ordering in a directed graph G = (V, E) with |V| = n nodes. In this setting, initially the edge-set E of the graph is empty. Subsequently, at each time-step an edge gets inserted into G. After every edge-insertion, we have to report if the current graph contains a cycle, and as long as the graph remains acyclic, we have to maintain a topological ordering of the node-set V. Let m be the total number of edges that get inserted into G. We present a randomized algorithm for this problem with Õ(m4/3) total expected update time.
Our result improves the Õ(m • min(m1/2, n2/3)) total update time bound of [5, 9, 10, 7]. In particular, for m = O(n), our result breaks the longstanding barrier on the total update time. Furthermore, whenever m = o(n3/2), our result improves upon the recently obtained total update time bound of [6]. We note that if m = Ω(n3/2), then the algorithm of [5, 4, 7], which has Õ(n2) total update time, beats the performance of the time algorithm of [6]. It follows that we improve upon the total update time of the algorithm of [6] in the “interesting” range of sparsity where m = o(n3/2).
Our result also happens to be the first one that breaks the lower bound of [9] on the total update time of any local algorithm for a nontrivial range of sparsity. Specifically, the total update time of our algorithm is whenever . From a technical perspective, we obtain our result by combining the algorithm of [6] with the balanced search framework of [10].
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||
| Divisions: | Faculty of Science > Computer Science | ||||||
| Library of Congress Subject Headings (LCSH): | Graph theory -- Data processing, Computer algorithms | ||||||
| Journal or Publication Title: | Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) | ||||||
| Publisher: | Society for Industrial and Applied Mathematics | ||||||
| ISBN: | 9781611975994 | ||||||
| Official Date: | January 2020 | ||||||
| Dates: |
|
||||||
| Page Range: | 2509-2521 | ||||||
| DOI: | 10.1137/1.9781611975994.153 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Publisher Statement: | Published in Proceedings of ACM-SIAM Symposium on Discrete Algorithms, published by the Society for Industrial and Applied Mathematics (SIAM) Copyright © 2020 by SIAM. Unauthorized reproduction of this article is prohibited. | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) | ||||||
| Type of Event: | Conference | ||||||
| Location of Event: | Salt Lake City, Utah, U.S. | ||||||
| Date(s) of Event: | 5-8 Jan 2020 | ||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
