Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
From MaRDI portal
Publication:849628
DOI10.1016/j.jda.2005.12.003zbMath1102.68512OpenAlexW1965948320WikidataQ61609584 ScholiaQ61609584MaRDI QIDQ849628
Camil Demetrescu, Giuseppe F. Italiano
Publication date: 31 October 2006
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2005.12.003
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (5)
Determining operations affected by delay in predictive train timetables ⋮ Reachability preserving compression for dynamic graph ⋮ Shortest distances as enumeration problem ⋮ Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time ⋮ Matrix representations and independencies in directed acyclic graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- Matrix multiplication via arithmetic progressions
- On-line computation of transitive closures of graphs
- Amortized efficiency of a path retrieval data structure
- Finding paths and deleting edges in directed acyclic graphs
- On the ratio of optimal integral and fractional covers
- Fast rectangular matrix multiplication and applications
- Semidynamic algorithms for maintaining single-source shortest path trees
- Speeding up dynamic transitive closure for bounded degree graphs
- On the computational complexity of dynamic graph problems
- On certificates and lookahead in dynamic graph problems
- Fully dynamic all pairs shortest paths with real edge weights
- Efficient determination of the transitive closure of a directed graph
- Maintaining Minimum Spanning Forests in Dynamic Graphs
- Randomized fully dynamic graph algorithms with polylogarithmic time per operation
- High-Probability Parallel Transitive-Closure Algorithms
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Improved Dynamic Reachability Algorithms for Directed Graphs
- Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O ( n 2 barrier
- A fully dynamic reachability algorithm for directed graphs with an almost linear update time
- Worst-case update times for fully-dynamic all-pairs shortest paths
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- A Greedy Heuristic for the Set-Covering Problem
- An On-Line Edge-Deletion Problem
- Incremental algorithms for minimal length paths
- An Incremental Algorithm for a Generalization of the Shortest-Path Problem
- Fully Dynamic Algorithms for Maintaining Shortest Paths Trees
- An Experimental Study of Dynamic Algorithms for Transitive Closure
- Algorithm Theory - SWAT 2004
- A new approach to dynamic all pairs shortest paths
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- The parametric problem of shortest distances
- Faster shortest-path algorithms for planar graphs
- A fully dynamic algorithm for maintaining the transitive closure
This page was built for publication: Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
