scientific article; zbMATH DE number 5899282

DOI10.4086/TOC.2009.V005A009MaRDI QIDQ3002808zbMATH OpenOpenAlexFDO

Authors Raphael Yuster, Virginia Vassilevska Williams, Ryan Williams

Publication date 24 May 2011

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2009.v005a009

zbMATH Keywords

bottleneck pathmatrix multiplicationmaximum capacity pathsubcubic time

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Fast algorithms for (, )-matrix multiplication and bottleneck shortest paths
• Subcubic cost algorithms for the all pairs shortest path problem
• An almost 2-approximation for all-pairs of shortest paths in subquadratic time
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• scientific article; zbMATH DE number 219247
• A new upper bound on the complexity of the all pairs shortest path problem
• Approximating all-pair bounded-leg shortest path and APSP-AF in truly-subcubic time
• Subcubic equivalences between path, matrix, and triangle problems
• Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover
• All-pairs shortest paths with a sublinear additive error

Cited in

(15)

• More on change-making and related problems
• Variations on the bottleneck paths problem
• Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
• All-pairs bottleneck paths in vertex weighted graphs
• Fast algorithms for (, )-matrix multiplication and bottleneck shortest paths
• Approximating all-pair bounded-leg shortest path and APSP-AF in truly-subcubic time
• Improved time bounds for all pairs non-decreasing paths in general digraphs
• Brief announcement: Hamming distance completeness and sparse matrix multiplication
• Hamming Distance Completeness
• Faster Algorithms for All Pairs Non-Decreasing Paths Problem
• Dominance product and high-dimensional closest pair under \(L_\infty\)
• scientific article; zbMATH DE number 7651168 (Why is no real title available?)
• Approximate min-sum subset convolution
• Removing the log factor from (,+)-products on bounded range integer matrices
• Non-Boolean OMv: one more reason to believe lower bounds for dynamic problems

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 Q3002808)