2017/10/11 by Christian Glazik, Glazik, Christian, Jan Schiemann +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Data Structures and Algorithms (cs.DS) #Discrete mathematics #Disjoint sets #Euler's formula #FOS: Computer and information sciences #Graph #Mathematical analysis #Mathematics #Merge (version control) #Optimization and Search Problems #Parallel computing #Running time #Stochastic processes and statistical mechanics #Successor cardinal #Undirected graph #cs.DS
paper · pdf · doi:10.48550/arxiv.1710.04091
published in arXiv (Cornell University) (Cornell University)
arxiv created 2017/10/11 · openalex publication_date 2017/10/11 · arxiv updated 2017/10/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
We study the problem of finding an Euler tour in an undirected graph G in the\nW-Streaming model with O(n polylog(n)) RAM, where n resp. m is the number of\nnodes resp. edges of G. Our main result is the first one pass W-Streaming\nalgorithm computing an Euler tour of G in the form of an edge successor\nfunction with only O(n log(n)) RAM which is optimal for this setting (e.g., Sun\nand Woodruff (2015)). The previously best-known result in this model is\nimplicitly given by Demetrescu et al. (2010) with the parallel algorithm of\nAtallah and Vishkin (1984) using O(m/n) passes under the same RAM limitation.\nFor graphs with \ω(n) edges this is non-constant. Our overall approach is\nto partition the edges into edge-disjoint cycles and to merge the cycles until\na single Euler tour is achieved. Note that in the W-Streaming model such a\nmerging is far from being obvious as the limited RAM allows the processing of\nonly a constant number of cycles at once. This enforces us to merge cycles that\npartially are no longer present in RAM. Furthermore, the successor of an edge\ncannot be changed after the edge has left RAM. So, we steadily have to output\nedges and their designated successors, not knowing the appearance of edges and\ncycles yet to come. We solve this problem with a special edge swapping\ntechnique, for which two certain edges per node are sufficient to merge tours\nwithout having all of their edges in RAM. Mathematically, this is controlled by\nstructural results on the space of certain equivalence classes corresponding to\ncycles and the characterization of associated successor functions. For example,\nwe give conditions under which the swapping of edge successors leads to a\nmerging of equivalence classes.\n