Undirected single-source shortest paths with positive integer weights in linear time
From MaRDI portal
Publication:3158540
DOI10.1145/316542.316548zbMath1065.68597OpenAlexW1999545213WikidataQ55923160 ScholiaQ55923160MaRDI QIDQ3158540
Publication date: 25 January 2005
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/316542.316548
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (58)
A new approach to all-pairs shortest paths on real-weighted graphs ⋮ Approximation algorithms for the optimal \(p\)-source communication spanning tree ⋮ An improved algorithm for the \(k\)-source maximum eccentricity spanning trees ⋮ A survey of the all-pairs shortest paths problem and its variants in graphs ⋮ A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes ⋮ Linear-Time Approximation for Maximum Weight Matching ⋮ An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths ⋮ A universal concept for robust solving of shortest path problems in dynamically reconfigurable graphs ⋮ Solving all-pairs shortest path by single-source computations: theory and practice ⋮ Shortest paths avoiding forbidden subpaths ⋮ Two fast algorithms for all-pairs shortest paths ⋮ Approximate distance oracles for graphs with dense clusters ⋮ On the second point-to-point undirected shortest simple path problem ⋮ Faster replacement paths algorithms in case of edge or node failure for undirected, positive integer weighted graphs ⋮ Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs ⋮ Continuous mean distance of a weighted graph ⋮ A weight-scaling algorithm for \(f\)-factors of multigraphs ⋮ Inserting Multiple Edges into a Planar Graph ⋮ A novel pseudo‐polynomial approach for shortest path problems ⋮ Complexity and approximation for discriminating and identifying code problems in geometric setups ⋮ A simpler and more efficient algorithm for the next-to-shortest path problem ⋮ Convex \(p\)-partitions of bipartite graphs ⋮ Path Laplacian matrices: introduction and application to the analysis of consensus in networks ⋮ Shortest paths in time-dependent FIFO networks ⋮ Shortest distances as enumeration problem ⋮ Balancing graph Voronoi diagrams with one more vertex ⋮ On bounded leg shortest paths problems ⋮ Faster cut sparsification of weighted graphs ⋮ On dynamic shortest paths problems ⋮ The saga of minimum spanning trees ⋮ Cycle bases in graphs characterization, algorithms, complexity, and applications ⋮ A survey of geodesic paths on 3D surfaces ⋮ An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path ⋮ Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs ⋮ Polynomial algorithms for guillotine cutting of a rectangle into small rectangles of two kinds ⋮ Minimum consistent subset of simple graph classes ⋮ On Algorithms Employing Treewidth for $L$-bounded Cut Problems ⋮ Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs ⋮ Hybrid Bellman-Ford-Dijkstra algorithm ⋮ The idemetric property: when most distances are (almost) the same ⋮ Discriminating Codes in Geometric Setups ⋮ Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners ⋮ Finding a minimum-depth embedding of a planar graph in \(O(n^{4})\) time ⋮ Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs ⋮ A spectral approach to the shortest path problem ⋮ Integer priority queues with decrease key in constant time and the single source shortest paths problem ⋮ An \(\tilde{O}(m^{2}n)\) algorithm for minimum cycle basis of graphs ⋮ Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation ⋮ A NOVEL LINEAR ALGORITHM FOR SHORTEST PATHS IN NETWORKS ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ Improved distance queries and cycle counting by Frobenius normal form ⋮ Faster algorithms for shortest path and network flow based on graph decomposition ⋮ A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing ⋮ Optimal centrality computations within bounded clique-width graphs ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ A Forward-Backward Single-Source Shortest Paths Algorithm ⋮ Unnamed Item ⋮ Linear-time parameterized algorithms with limited local resources
This page was built for publication: Undirected single-source shortest paths with positive integer weights in linear time
