We study the problem of finding an Euler tour in an undirected graph G in the W-Streaming model with O(n polylog(n)) RAM, where n, m are the number of nodes, edges of G. Our main result is the first one pass W-Streaming algorithm computing an Euler tour of G in the form of an edge successor function with only O(n log(n)) RAM which is optimal for this setting (e.g., Sun and Woodruff (2015)). The previously best-known result in this model is implicitly given by Demetrescu et al. (2010) with the parallel algorithm of Atallah and Vishkin (1984) using O(m/n) passes under the same RAM limitation. For graphs with omega(n) edges this is non-constant. Our overall approach is to partition the edges into edge-disjoint cycles and to merge the cycles until a single Euler tour is achieved. Note that in the W-Streaming model such a merging is far from being obvious as the limited RAM allows the processing of only a constant number of cycles at once. This enforces us to merge cycles that partially are no longer present in RAM. Furthermore, the successor of an edge cannot be changed after the edge has left RAM. So, we steadily have to output edges and their designated successors, not knowing the appearance of edges and cycles yet to come. We solve this problem with a special edge swapping technique, for which two certain edges per node are sufficient to merge tours without having all of their edges in RAM. Mathematically, this is controlled by structural results on the space of certain equivalence classes corresponding to cycles and the characterization of associated successor functions. For example, we give conditions under which the swapping of edge successors leads to a merging of equivalence classes. The mathematical methods of our analysis are new and might be of independent interest for other routing problems in streaming models. Joint work with Christian Glazik, Jan Schiemann
Anand Srivastav studied Mathematics and Physics at the University of Münster. In 1988 he completed his doctoral dissertation in Mathematics, with focus on Functional Analysis. Thereafter he changed the research focus to Discrete Mathematics and Optimization and in this respect he was holding postdoc und assistant professor positions at University Bonn, University of Minnesota, New York University, Yale University and FU Berlin, where he completed the habilitation 1996 in computer science, with focus on algorithmic discrete mathematics. Since 1997 he has been professor for Discrete Optimization at the Engineering Faculty of Kiel University, Department of Computer Science. Anand Srivastav is speaker of the research platforms in the cluster of excellence ‘Future Ocean’. In 2013 he has been awarded the Indo-German Max Planck guest professorship of the Max-Planck-Society (MPG). More Details about the speaker are available at https://www.kms.uni-kiel.de/en/team/auf-einen-blick-mitglieder-kms-1/prof.-dr.-rer.-nat.-anand-srivastav.