Streaming complexity of spanning tree computation

Yi Jun Chang*, Martín Farach-Colton, Tsan Sheng Hsu, Meng Tsung Tsai

*Corresponding author for this work

研究成果: Conference contribution同行評審

摘要

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.

原文English
主出版物標題37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020
編輯Christophe Paul, Markus Blaser
發行者Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
154
ISBN(電子)9783959771405
DOIs
出版狀態Published - 2020
事件37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020 - Montpellier, France
持續時間: 10 三月 202013 三月 2020

出版系列

名字Leibniz International Proceedings in Informatics, LIPIcs
154
ISSN(列印)1868-8969

Conference

Conference37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020
國家France
城市Montpellier
期間10/03/2013/03/20

指紋 深入研究「Streaming complexity of spanning tree computation」主題。共同形成了獨特的指紋。

引用此