Undirected single-source shortest paths with positive integer weights in linear time
From MaRDI portal
Recommendations
- A Shortest Path Algorithm for Real-Weighted Undirected Graphs
- Single-source shortest-paths on arbitrary directed graphs in linear average-case time
- A faster algorithm for the single source shortest path problem with few distinct positive lengths
- Algorithms – ESA 2005
- A Randomized Parallel Algorithm for Single-Source Shortest Paths
Cited in
(68)- Improved distance queries and cycle counting by Frobenius normal form
- Shortest beer path queries based on graph decomposition
- On the second point-to-point undirected shortest simple path problem
- Path Laplacian matrices: introduction and application to the analysis of consensus in networks
- A survey of geodesic paths on 3D surfaces
- Discriminating Codes in Geometric Setups
- Linear-time parameterized algorithms with limited local resources
- Shortest paths avoiding forbidden subpaths
- Cycle bases in graphs characterization, algorithms, complexity, and applications
- Directed shortest paths via approximate cost balancing
- A survey of the all-pairs shortest paths problem and its variants in graphs
- Two fast algorithms for all-pairs shortest paths
- A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
- Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs
- Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
- 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
- Polynomial algorithms for guillotine cutting of a rectangle into small rectangles of two kinds
- Single source shortest paths in H-minor free graphs
- scientific article; zbMATH DE number 1766771 (Why is no real title available?)
- Continuous mean distance of a weighted graph
- Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
- Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs
- A spectral approach to the shortest path problem
- A weight-scaling algorithm for \(f\)-factors of multigraphs
- A novel pseudo‐polynomial approach for shortest path problems
- An improved algorithm for the k-source maximum eccentricity spanning trees
- On algorithms employing treewidth for L-bounded cut problems
- Approximate distance oracles for graphs with dense clusters
- scientific article; zbMATH DE number 7121921 (Why is no real title available?)
- Networks cannot compute their diameter in sublinear time
- Solving all-pairs shortest path by single-source computations: theory and practice
- The saga of minimum spanning trees
- A new approach to all-pairs shortest paths on real-weighted graphs
- Linear-time approximation for maximum weight matching
- Shortest distances as enumeration problem
- Faster algorithms for shortest path and network flow based on graph decomposition
- A forward-backward single-source shortest paths algorithm
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
- Faster replacement paths algorithms in case of edge or node failure for undirected, positive integer weighted graphs
- A universal concept for robust solving of shortest path problems in dynamically reconfigurable graphs
- Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
- Balancing graph Voronoi diagrams with one more vertex
- Minimum consistent subset of simple graph classes
- Inserting Multiple Edges into a Planar Graph
- On bounded leg shortest paths problems
- On dynamic shortest paths problems
- A simpler and more efficient algorithm for the next-to-shortest path problem
- An O(n^3 n / ^2 n) time algorithm for all pairs shortest paths
- A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing
- The idemetric property: when most distances are (almost) the same
- Shortest paths in time-dependent FIFO networks
- A novel single source shortest path algorithm
- An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
- Approximation algorithms for the optimal \(p\)-source communication spanning tree
- Negative-weight single-source shortest paths in near-linear time
- Faster cut sparsification of weighted graphs
- Complexity and approximation for discriminating and identifying code problems in geometric setups
- Hybrid Bellman-Ford-Dijkstra algorithm
- Bypassing Erdős' girth conjecture: hybrid stretch and sourcewise spanners
- Exploring monotone priority queues for Dijkstra optimization
- Convex \(p\)-partitions of bipartite graphs
- A faster algorithm for the single source shortest path problem with few distinct positive lengths
- Average-case and smoothed analysis of graph isomorphism
- Single-source shortest-paths on arbitrary directed graphs in linear average-case time
- Optimal centrality computations within bounded clique-width graphs
- Finding a minimum-depth embedding of a planar graph in \(O(n^{4})\) time
- A novel linear algorithm for shortest paths in networks
This page was built for publication: Undirected single-source shortest paths with positive integer weights in linear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3158540)
