scientific article; zbMATH DE number 5485494

MaRDI QIDQ3549658zbMATH OpenFDO

Authors Raphael Yuster, Virginia Vassilevska Williams, Ryan Williams

Publication date 5 January 2009

zbMATH Keywords

all-pairs bottleneck paths problemall-pairs maximum capacity paths problem

Mathematics Subject Classification ID

Flows in graphs (05C21) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40)

Cited in

(10)

• The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis
• Approximating all-pair bounded-leg shortest path and APSP-AF in truly-subcubic time
• Single-source bottleneck path algorithm faster than sorting for sparse graphs
• On Cartesian trees and range minimum queries
• Quadratic bottleneck problems
• All-pairs bottleneck paths in vertex weighted graphs
• Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
• On efficient algorithms for bottleneck path problems with many sources
• Algorithms, reductions and equivalences for small weight variants of all-pairs shortest paths
• Bottleneck flows in unit capacity networks

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3549658)