Chechik, Shiri ;
Kaplan, Haim ;
Thorup, Mikkel ;
Zamir, Or ;
Zwick, Uri
Bottleneck Paths and Trees and Deterministic Graphical Games
Abstract
Gabow and Tarjan showed that the Bottleneck Path (BP) problem, i.e., finding a path between a given source and a given target in a weighted directed graph whose largest edge weight is minimized, as well as the Bottleneck spanning tree (BST) problem, i.e., finding a directed spanning tree rooted at a given vertex whose largest edge weight is minimized, can both be solved deterministically in O(m * log^*(n)) time, where m is the number of edges and n is the number of vertices in the graph. We present a slightly improved randomized algorithm for these problems with an expected running time of O(m * beta(m,n)), where beta(m,n) = min{k >= 1  log^{(k)}n <= m/n } <= log^*(n)  log^*(m/n)+1. This is the first improvement for these problems in over 25 years. In particular, if m >= n * log^{(k)} * n, for some constant k, the expected running time of the new algorithm is O(m). Our algorithm, as that of Gabow and Tarjan, work in the comparison model. We also observe that in the wordRAM model, both problems can be solved deterministically in O(m) time. Finally, we solve an open problem of Andersson et al., giving a deterministic O(m)time comparisonbased algorithm for solving deterministic 2player turnbased zerosum terminal payoff games, also known as Deterministic Graphical Games (DGG).
BibTeX  Entry
@InProceedings{chechik_et_al:LIPIcs:2016:5728,
author = {Shiri Chechik and Haim Kaplan and Mikkel Thorup and Or Zamir and Uri Zwick},
title = {{Bottleneck Paths and Trees and Deterministic Graphical Games}},
booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages = {27:127:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770019},
ISSN = {18688969},
year = {2016},
volume = {47},
editor = {Nicolas Ollinger and Heribert Vollmer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5728},
URN = {urn:nbn:de:0030drops57283},
doi = {10.4230/LIPIcs.STACS.2016.27},
annote = {Keywords: bottleneck paths, comparison model, deterministic graphical games}
}
16.02.2016
Keywords: 

bottleneck paths, comparison model, deterministic graphical games 
Seminar: 

33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Issue date: 

2016 
Date of publication: 

16.02.2016 