Shortest paths in multimode graphs

DOI10.4230/LIPICS.MFCS.2025.63MaRDI QIDQ7310238zbMATH OpenFDO

Authors Yael Kirkpatrick, Virginia Vassilevska Williams

Publication date 5 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2025.63

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Algorithms – ESA 2004
• Approximating min-diameter: standard and bichromatic
• Approximation algorithms for min-distance problems
• Approximation algorithms for min-distance problems in DAGs
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Better approximation algorithms for the graph diameter
• Constant approximation of min-distances in near-linear time
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Hardness of approximate diameter: now for undirected graphs
• scientific article; zbMATH DE number 1305501 (Why is no real title available?)
• New bounds for approximating extremal distances in undirected graphs
• New bounds for matrix multiplication: from alpha to omega
• On the complexity of k-SAT
• On the exact complexity of evaluating quantified k-CNF
• Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
• Tight conditional lower bounds for approximating diameter in directed graphs
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities

This page was built for publication: Shortest paths in multimode graphs

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