A one pass streaming algorithm for finding Euler tours

DOI10.1007/S00224-022-10077-WMaRDI QIDQ6174649zbMATH OpenOpenAlexFDO

Authors Christian Glazik, Jan Schiemann, Anand Srivastav

Publication date 17 August 2023

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

graph theorystreaming algorithmbig datadata streamEuler tours

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
• An Eulerian path approach to DNA fragment assembly
• Automata, Languages and Programming
• Finding Euler tours in parallel
• On graph problems in a semi-streaming model
• Tight bounds for graph problems in insertion streams
• Trading off space for passes in graph streaming problems
• Unidirectional input/output streaming complexity of reversal and sorting
• Worst-case analysis of a new heuristic for the travelling salesman problem

Cited in

(1)

• Low-memory algorithms for online edge coloring

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6174649)