A one pass streaming algorithm for finding Euler tours

DOI10.1007/s00224-022-10077-wOpenAlexW4312131249MaRDI QIDQ6174649

Jan Schiemann, Anand Srivastav, Christian Glazik

Publication date: 17 August 2023

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-022-10077-w

zbMATH Keywords

graph theoryEuler toursbig datadata streamstreaming algorithm

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Graph theory (05Cxx)

Cites Work

• Adapting parallel algorithms to the W-stream model, with applications to graph problems
• Finding Euler tours in parallel
• Worst-case analysis of a new heuristic for the travelling salesman problem
• On graph problems in a semi-streaming model
• Unidirectional Input/Output Streaming Complexity of Reversal and Sorting
• An Eulerian path approach to DNA fragment assembly
• Tight Bounds for Graph Problems in Insertion Streams
• Automata, Languages and Programming
• Trading off space for passes in graph streaming problems

This page was built for publication: A one pass streaming algorithm for finding Euler tours