2026-07-25T01:23:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6398 2024-03-06T10:38:10Z ddc:004 open_access

A Streaming Algorithm for the Undirected Longest Path Problem Kliemann, Lasse Schielke, Christian Srivastav, Anand Streaming Algorithms Undirected Longest Path Problem Graph Algorithms Combinatorial Optimization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lasse Kliemann and Christian Schielke and Anand Srivastav 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.56 urn:nbn:de:0030-drops-63980 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.56 eng https://creativecommons.org/licenses/by/3.0/legalcode