Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.56
URN: urn:nbn:de:0030-drops-63980
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6398/
Kliemann, Lasse ; Schielke, Christian ; Srivastav, Anand
A Streaming Algorithm for the Undirected Longest Path Problem
| pdf-format: |
|
Abstract
We present the first streaming algorithm for the longest path problem in undirected graphs. The input graph is given as a stream of edges and RAM is limited to only a linear number of edges at a time (linear in the number of vertices n). We prove a per-edge processing time of O(n), where a naive solution would have required Omega(n^2). Moreover, we give a concrete linear upper bound on the number of bits of RAM that are required.On a set of graphs with various structure, we experimentally compare our algorithm with three leading RAM algorithms: Warnsdorf (1823), Pohl-Warnsdorf (1967), and Pongrasz (2012). Although conducting only a small constant number of passes over the input, our algorithm delivers competitive results: with the exception of preferential attachment graphs, we deliver at least 71% of the solution of the best RAM algorithm. The same minimum relative performance of 71% is observed over all graph classes after removing the 10% worst cases. This comparison has strong meaning, since for each instance class there is one algorithm that on average delivers at least 84% of a Hamilton path. In some cases we deliver even better results than any of the RAM algorithms.
BibTeX - Entry
@InProceedings{kliemann_et_al:LIPIcs:2016:6398,
author = {Lasse Kliemann and Christian Schielke and Anand Srivastav},
title = {{A Streaming Algorithm for the Undirected Longest Path Problem}},
booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)},
pages = {56:1--56:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-015-6},
ISSN = {1868-8969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6398},
URN = {urn:nbn:de:0030-drops-63980},
doi = {10.4230/LIPIcs.ESA.2016.56},
annote = {Keywords: Streaming Algorithms, Undirected Longest Path Problem, Graph Algorithms, Combinatorial Optimization}
}
| Keywords: | Streaming Algorithms, Undirected Longest Path Problem, Graph Algorithms, Combinatorial Optimization | |
| Seminar: | 24th Annual European Symposium on Algorithms (ESA 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 18.08.2016 |
