Single-source shortest paths and strong connectivity in dynamic planar graphs
- 1 March 2022
- journal article
- research article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 124, 97-111
Abstract
No abstract availableKeywords
Funding Information
- A.G. Leventis Foundation
- Narodowe Centrum Nauki (2018/29/N/ST6/00757)
- European Research Council (677651)
- European Research Council (772346 TUgbOAT)
- European Research Council
- Fundacja na rzecz Nauki Polskiej
- Israel Science Foundation (592/17)
This publication has 25 references indexed in Scilit:
- Multiple-Source Shortest Paths in Embedded GraphsSIAM Journal on Computing, 2013
- Many Distances in Planar GraphsAlgorithmica, 2010
- Shortest paths in directed planar graphs with negative lengthsACM Transactions on Algorithms, 2010
- An O ( n log n ) algorithm for maximum st -flow in a directed planar graphJournal of the ACM, 2009
- Improved decremental algorithms for maintaining transitive closure and all-pairs shortest pathsJournal of Algorithms, 2007
- Approximate distance oraclesJournal of the ACM, 2005
- Compact oracles for reachability and approximate distances in planar digraphsJournal of the ACM, 2004
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivityJournal of the ACM, 2001
- Separator Based SparsificationJournal of Computer and System Sciences, 1996
- Maintenance of a minimum spanning forest in a dynamic plane graphJournal of Algorithms, 1992