Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
type: Item
instance of: scholarly article
title: Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
zbMATH Open document ID: 1102.68512
author: Camil Demetrescu
author: Giuseppe F. Italiano
published in: Journal of Discrete Algorithms
publication date: 2006-10-31T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 5069045
zbMATH Keywords: dynamic graph algorithms
zbMATH Keywords: shortest paths
MaRDI profile type: Publication
full work available at URL: j.jda.2005.12.003
OpenAlex ID: W1965948320
Wikidata QID: Q61609584
cites work: Q4091421
cites work: Incremental algorithms for minimal length paths
cites work: A Greedy Heuristic for the Set-Covering Problem
cites work: Matrix multiplication via arithmetic progressions
cites work: Q3619797
cites work: A new approach to dynamic all pairs shortest paths
cites work: Q5501281
cites work: Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O ( n 2 barrier
cites work: Fully dynamic all pairs shortest paths with real edge weights
cites work: A note on two problems in connexion with graphs
cites work: Q3679232
cites work: An On-Line Edge-Deletion Problem
cites work: Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
cites work: Semidynamic algorithms for maintaining single-source shortest path trees
cites work: Fully Dynamic Algorithms for Maintaining Shortest Paths Trees
cites work: An Experimental Study of Dynamic Algorithms for Transitive Closure
cites work: Q5616737
cites work: Q4252752
cites work: Maintaining minimum spanning forests in dynamic graphs
cites work: Randomized fully dynamic graph algorithms with polylogarithmic time per operation
cites work: Faster shortest-path algorithms for planar graphs
cites work: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
cites work: Fast rectangular matrix multiplication and applications
cites work: On-line computation of transitive closures of graphs
cites work: Amortized efficiency of a path retrieval data structure
cites work: Finding paths and deleting edges in directed acyclic graphs
cites work: On certificates and lookahead in dynamic graph problems
cites work: A fully dynamic algorithm for maintaining the transitive closure
cites work: Q4553236
cites work: Q3813313
cites work: On the ratio of optimal integral and fractional covers
cites work: Efficient determination of the transitive closure of a directed graph
cites work: An Incremental Algorithm for a Generalization of the Shortest-Path Problem
cites work: On the computational complexity of dynamic graph problems
cites work: The parametric problem of shortest distances
cites work: Improved Dynamic Reachability Algorithms for Directed Graphs
cites work: A fully dynamic reachability algorithm for directed graphs with an almost linear update time
cites work: Q3685214
cites work: Algorithm Theory - SWAT 2004
cites work: Worst-case update times for fully-dynamic all-pairs shortest paths
cites work: High-Probability Parallel Transitive-Closure Algorithms
cites work: Speeding up dynamic transitive closure for bounded degree graphs
cites work: All pairs shortest paths using bridging sets and rectangular matrix multiplication
DOI: 10.1016/J.JDA.2005.12.003
DBLP publication ID: journals/jda/DemetrescuI06
description: scientific article; zbMATH DE number 5069045