In the Euler tour problem, we are looking for a closed Footnote 1 trail in an undirected graph G = ( V, E), where n = | V | and m = | E|, such that each edge is visited exactly once. This quite general approach might be of interest also in other routing problems.ġ.1 Euler Tours in the Graph-Streaming Model The mathematical key is to model tours and their merging in an algebraic way, where certain equivalence classes represent subtours. We solve this problem with a new edge swapping technique, for which storing two certain edges per node is sufficient to merge tours without having all tour edges in RAM. This enforces merging of cycles that partially are no longer present in RAM. In the streaming environment such a merging is far from being obvious as the limited RAM allows the processing of only a constant number of cycles at once. Our approach is to partition the edges into edge-disjoint cycles and to merge the cycles until a single Euler tour is achieved. (2010) using \(\mathcal O(m/n)\) passes under the same RAM limitation. The previously best-known result for finding Euler tours in data streams is implicitly given by the W-stream algorithm of Demetrescu et al. Since the output size can be much larger, we use a write-only tape to gradually output the solution. Our main result is the first one-pass streaming algorithm computing an Euler tour of G in the form of an edge successor function with only \(\mathcal O(n\log (n))\) RAM, which is optimal for this setting (e.g. Given an undirected graph G on n nodes and m edges in the form of a data stream we study the problem of finding an Euler tour in G.
0 kommentar(er)
