Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

[img]
Preview
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

Request Changes to record.

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:
DateEvent
January 2020Available
24 September 2019Accepted
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:
  • Publisher

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us