TY - GEN

T1 - Streaming complexity of spanning tree computation

AU - Chang, Yi Jun

AU - Farach-Colton, Martín

AU - Hsu, Tsan Sheng

AU - Tsai, Meng Tsung

N1 - Publisher Copyright:
© Yi-Jun Chang, Martín Farach-Colton, Tsan-Sheng Hsu, and Meng-Tsung Tsai; licensed under Creative Commons License CC-BY

PY - 2020

Y1 - 2020

N2 - The semi-streaming model is a variant of the streaming model frequently used for the computation of graph problems. It allows the edges of an n-node input graph to be read sequentially in p passes using Õ(n) space. If the list of edges includes deletions, then the model is called the turnstile model; otherwise it is called the insertion-only model. In both models, some graph problems, such as spanning trees, k-connectivity, densest subgraph, degeneracy, cut-sparsifier, and (∆ + 1)-coloring, can be exactly solved or (1 + ε)-approximated in a single pass; while other graph problems, such as triangle detection and unweighted all-pairs shortest paths, are known to require Ω (n) passes to compute. For many fundamental graph problems, the tractability in these models is open. In this paper, we study the tractability of computing some standard spanning trees, including BFS, DFS, and maximum-leaf spanning trees. Our results, in both the insertion-only and the turnstile models, are as follows.

AB - The semi-streaming model is a variant of the streaming model frequently used for the computation of graph problems. It allows the edges of an n-node input graph to be read sequentially in p passes using Õ(n) space. If the list of edges includes deletions, then the model is called the turnstile model; otherwise it is called the insertion-only model. In both models, some graph problems, such as spanning trees, k-connectivity, densest subgraph, degeneracy, cut-sparsifier, and (∆ + 1)-coloring, can be exactly solved or (1 + ε)-approximated in a single pass; while other graph problems, such as triangle detection and unweighted all-pairs shortest paths, are known to require Ω (n) passes to compute. For many fundamental graph problems, the tractability in these models is open. In this paper, we study the tractability of computing some standard spanning trees, including BFS, DFS, and maximum-leaf spanning trees. Our results, in both the insertion-only and the turnstile models, are as follows.

KW - BFS Trees

KW - DFS Trees

KW - Max-Leaf Spanning Trees

UR - http://www.scopus.com/inward/record.url?scp=85082111947&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.STACS.2020.34

DO - 10.4230/LIPIcs.STACS.2020.34

M3 - Conference contribution

AN - SCOPUS:85082111947

VL - 154

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020

A2 - Paul, Christophe

A2 - Blaser, Markus

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020

Y2 - 10 March 2020 through 13 March 2020

ER -