Kliemann, Lasse ;
Schielke, Christian ;
Srivastav, Anand
A Streaming Algorithm for the Undirected Longest Path Problem
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 peredge 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), PohlWarnsdorf (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:156:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770156},
ISSN = {18688969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6398},
URN = {urn:nbn:de:0030drops63980},
doi = {10.4230/LIPIcs.ESA.2016.56},
annote = {Keywords: Streaming Algorithms, Undirected Longest Path Problem, Graph Algorithms, Combinatorial Optimization}
}
2016
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: 

2016 