DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2016.56

A Streaming Algorithm for the Undirected Longest Path Problem

Authors: Lasse Kliemann, Christian Schielke, and Anand Srivastav

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

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.

Cite as

Lasse Kliemann, Christian Schielke, and Anand Srivastav. A Streaming Algorithm for the Undirected Longest Path Problem. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 56:1-56:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kliemann_et_al:LIPIcs.ESA.2016.56,
  author =	{Kliemann, Lasse and Schielke, Christian and Srivastav, Anand},
  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 =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.56},
  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}
}

Search Results

Documents authored by Schielke, Christian

A Streaming Algorithm for the Undirected Longest Path Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message