Improved Deterministic Algorithms for Decremental Reachability and Strongly Connected Components
Author:
Open Access
- 1 June 2013
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 9 (3) , 1-15
Abstract
This article presents a new deterministic algorithm for decremental maintenance of the transitive closure in a directed graph. The algorithm processes any sequence of edge deletions in O ( mn ) time and answers queries in constant time. Previously, such time bound has only been achieved by a randomized Las Vegas algorithm. In addition to that, a few decremental algorithms for maintaining strongly connected components are shown, whose time complexity is O ( n 1.5 ) for planar graphs, O ( n log n ) for graphs with bounded treewidth and O ( mn ) for general digraphs.Keywords
This publication has 11 references indexed in Scilit:
- Decremental maintenance of strongly connected components2013
- Fast Dynamic Transitive Closure with LookaheadAlgorithmica, 2008
- Improved Dynamic Reachability Algorithms for Directed GraphsSIAM Journal on Computing, 2008
- Improved decremental algorithms for maintaining transitive closure and all-pairs shortest pathsJournal of Algorithms, 2007
- Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O ( n 2 barrierJournal of the ACM, 2005
- An Experimental Study of Dynamic Algorithms for Transitive ClosureACM Journal of Experimental Algorithmics, 2001
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small TreewidthSIAM Journal on Computing, 1996
- Finding paths and deleting edges in directed acyclic graphsInformation Processing Letters, 1988
- Maintenance of transitive closures and transitive reductions of graphsLecture Notes in Computer Science, 1988
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979