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
(71)- 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 generalization of Dijkstra's shortest path algorithm with applications to VLSI routing
- A universal concept for robust solving of shortest path problems in dynamically reconfigurable graphs
- Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs
- 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 simpler and more efficient algorithm for the next-to-shortest path problem
- A spectral approach to the shortest path problem
- Optimal centrality computations within bounded clique-width graphs
- Linear-time parameterized algorithms with limited local resources
- Improved distance queries and cycle counting by Frobenius normal form
- Solving all-pairs shortest path by single-source computations: theory and practice
- Shortest paths in time-dependent FIFO networks
- Polynomial algorithms for guillotine cutting of a rectangle into small rectangles of two kinds
- A survey of the all-pairs shortest paths problem and its variants in graphs
- Faster cut sparsification of weighted graphs
- Single-source shortest-paths on arbitrary directed graphs in linear average-case time
- A novel linear algorithm for shortest paths in networks
- Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
- Linear-time approximation for maximum weight matching
- An O(n^3 n / ^2 n) time algorithm for all pairs shortest paths
- A novel single source shortest path algorithm
- 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
- Path Laplacian matrices: introduction and application to the analysis of consensus in networks
- Floats, Integers, and Single Source Shortest Paths
- scientific article; zbMATH DE number 1766771 (Why is no real title available?)
- The saga of minimum spanning trees
- Cycle bases in graphs characterization, algorithms, complexity, and applications
- On algorithms employing treewidth for L-bounded cut problems
- Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
- Hybrid Bellman-Ford-Dijkstra algorithm
- The idemetric property: when most distances are (almost) the same
- Bypassing Erdős' girth conjecture: hybrid stretch and sourcewise spanners
- scientific article; zbMATH DE number 7121921 (Why is no real title available?)
- Faster algorithms for shortest path and network flow based on graph decomposition
- A forward-backward single-source shortest paths algorithm
- A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
- Shortest paths avoiding forbidden subpaths
- Finding a minimum-depth embedding of a planar graph in \(O(n^{4})\) time
- Networks cannot compute their diameter in sublinear time
- Integer priority queues with decrease key in constant time and the single source shortest paths problem
- Continuous mean distance of a weighted graph
- A weight-scaling algorithm for \(f\)-factors of multigraphs
- Discriminating Codes in Geometric Setups
- 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
- Minimum consistent subset of simple graph classes
- Shortest distances as enumeration problem
- Balancing graph Voronoi diagrams with one more vertex
- On bounded leg shortest paths problems
- On dynamic shortest paths problems
- A survey of geodesic paths on 3D surfaces
- Directed shortest paths via approximate cost balancing
- Negative-weight single-source shortest paths in near-linear time
- Exploring monotone priority queues for Dijkstra optimization
- Shortest beer path queries based on graph decomposition
- Average-case and smoothed analysis of graph isomorphism
- Fault-tolerant ST-diameter oracles
- Testing whether a subgraph is convex or isometric
- Two fast algorithms for all-pairs shortest paths
- Approximate distance oracles for graphs with dense clusters
- Convex \(p\)-partitions of bipartite graphs
- An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
- A faster algorithm for the single source shortest path problem with few distinct positive lengths
- Single source shortest paths in H-minor free graphs
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)
