A Streaming Algorithm for the Undirected Longest Path Problem.

Kliemann, Lasse , Schielke, Christian and Srivastav, Anand (2016) A Streaming Algorithm for the Undirected Longest Path Problem. In: 24th Annual European Symposium on Algorithms (ESA 2016). . Leibniz International Proceedings in Informatics (LIPIcs), 57 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 56:1-56:17. ISBN 978-3-95977-015-6

Full text not available from this repository.

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
Ω(
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 Pongrácz (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.

Document Type: Book chapter
Research affiliation: Kiel University > Kiel Marine Science
OceanRep > The Future Ocean - Cluster of Excellence
Kiel University
Publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Projects: Future Ocean
Date Deposited: 18 Jan 2017 10:06
Last Modified: 23 Sep 2019 17:20
URI: https://oceanrep.geomar.de/id/eprint/35687

Actions (login required)

View Item View Item