A survey of the all-pairs shortest paths problem and its variants in graphs
From MaRDI portal
Publication:2629565
DOI10.1515/ausi-2016-0002zbMath1362.68236OpenAlexW2468306032MaRDI QIDQ2629565
Publication date: 6 July 2016
Published in: Acta Universitatis Sapientiae. Informatica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1515/ausi-2016-0002
Extremal problems in graph theory (05C35) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph theory (including graph drawing) in computer science (68R10) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (1)
Cites Work
- A note on two problems in connexion with graphs
- Average distance in weighted graphs
- Matrix multiplication via arithmetic progressions
- On the minimum average distance spanning tree of the hypercube
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- A linear-time algorithm to compute a MAD tree of an interval graph
- A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing
- A new upper bound on the complexity of the all pairs shortest path problem
- Mean distance in a graph
- Average distance and independence number
- Computing the average distance of an interval graph
- On the exponent of all pairs shortest path problem
- All pairs shortest distances for graphs with small integer length edges
- Unified all-pairs shortest path algorithms in the chordal hierarchy
- Average distance and domination number
- Wiener number of vertex-weighted graphs and a chemical application
- MAD trees and distance-hereditary graphs
- Distances in benzenoid systems: Further developments
- Wiener index of hexagonal systems
- An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs
- A conjecture on Wiener indices in combinatorial chemistry
- A new approach to all-pairs shortest paths on real-weighted graphs
- Clique partitions, graph compression and speeding-up algorithms
- All-pairs-shortest-length on strongly chordal graphs
- Improved algorithm for all pairs shortest paths
- All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
- Gaussian elimination is not optimal
- An O(n 3 loglogn/log2 n) Time Algorithm for All Pairs Shortest Paths
- Minimum Average Distance Clique Trees
- Using Selective Path-Doubling for Parallel Shortest-Path Computations
- Undirected single-source shortest paths with positive integer weights in linear time
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- A New Combinatorial Approach for Sparse Graph Problems
- More algorithms for all-pairs shortest paths in weighted graphs
- All-pairs shortest paths for unweighted undirected graphs in o(mn) time
- The average distance and the independence number
- An optimal algorithm to solve the all-pair shortest path problem on interval graphs
- A more efficient algorithm for the min-plus multiplication
- New Bounds on the Complexity of the Shortest Path Problem
- Distance in graphs
- Efficient Algorithms for Shortest Paths in Sparse Networks
- The complexity of the network design problem
- All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
- Interactive Segmentation with Intelligent Scissors
- Graph Classes: A Survey
- Polylog-time and near-linear work approximation scheme for undirected shortest paths
- Computing and Combinatorics
- A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
- Fibonacci heaps and their uses in improved network optimization algorithms
- A Shortest Path Algorithm for Real-Weighted Undirected Graphs
- Combining All Pairs Shortest Paths and All Pairs Bottleneck Paths Problems
- Multiplying matrices faster than coppersmith-winograd
- An O(n 3 (loglogn/logn)5/4) Time Algorithm for All Pairs Shortest Paths
- Average Distance, Independence Number, and Spanning Trees
- Estimating all pairs shortest paths in restricted graph families: a unified approach
- Algorithms and Computation
- Faster shortest-path algorithms for planar graphs
- Integer priority queues with decrease key in constant time and the single source shortest paths problem
- Wiener index of trees: Theory and applications
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A survey of the all-pairs shortest paths problem and its variants in graphs
