All-pairs bottleneck paths in vertex weighted graphs
From MaRDI portal
Publication:633850
DOI10.1007/s00453-009-9328-xzbMath1211.05168OpenAlexW3137337592MaRDI QIDQ633850
Uri Zwick, Raphael Yuster, Asaf Shapira
Publication date: 30 March 2011
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-009-9328-x
Analysis of algorithms (68W40) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)
Related Items (5)
Quantum and approximation algorithms for maximum witnesses of Boolean matrix products ⋮ Extreme Witnesses and Their Applications ⋮ Efficient parameterized algorithms for computing all-pairs shortest paths ⋮ Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs ⋮ Extreme witnesses and their applications
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Matrix multiplication via arithmetic progressions
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- Witnesses for Boolean matrix multiplication and for transitive closure
- Fast rectangular matrix multiplication and applications
- Rectangular matrix multiplication revisited
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Faster algorithms for finding lowest common ancestors in directed acyclic graphs
- Efficient determination of the transitive closure of a directed graph
- All pairs lightest shortest paths
- Finding a maximum weight triangle in n 3-Δ time, with applications
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems
- Algorithms for two bottleneck optimization problems
- Lowest common ancestors in trees and directed acyclic graphs
- Automata, Languages and Programming
This page was built for publication: All-pairs bottleneck paths in vertex weighted graphs
