License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.42
URN: urn:nbn:de:0030-drops-90467
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9046/
Duan, Ran ;
Ren, Hanlin
Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time
Abstract
In the bounded-leg shortest path (BLSP) problem, we are given a weighted graph G with nonnegative edge lengths, and we want to answer queries of the form "what's the shortest path from u to v, where only edges of length <=L are considered?". A more general problem is the APSP-AF (all-pair shortest path for all flows) problem, in which each edge has two weights - a length d and a capacity f, and a query asks about the shortest path from u to v where only edges of capacity >= f are considered.
In this article we give an O~(n^{(omega+3)/2}epsilon^{-3/2}log W) time algorithm to compute a data structure that answers APSP-AF queries in O(log(epsilon^{-1}log (nW))) time and achieves (1+epsilon)-approximation, where omega < 2.373 is the exponent of time complexity of matrix multiplication, W is the upper bound of integer edge lengths, and n is the number of vertices. This is the first truly-subcubic time algorithm for these problems on dense graphs. Our algorithm utilizes the O(n^{(omega+3)/2}) time max-min product algorithm [Duan and Pettie 2009]. Since the all-pair bottleneck path (APBP) problem, which is equivalent to max-min product, can be seen as all-pair reachability for all flow, our approach indeed shows that these problems are almost equivalent in the approximation sense.
BibTeX - Entry
@InProceedings{duan_et_al:LIPIcs:2018:9046,
author = {Ran Duan and Hanlin Ren},
title = {{Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {42:1--42:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-076-7},
ISSN = {1868-8969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9046},
URN = {urn:nbn:de:0030-drops-90467},
doi = {10.4230/LIPIcs.ICALP.2018.42},
annote = {Keywords: Graph Theory, Approximation Algorithms, Combinatorial Optimization}
}
|
Keywords: |
|
Graph Theory, Approximation Algorithms, Combinatorial Optimization |
|
Collection: |
|
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
04.07.2018 |
