Streaming complexity of spanning tree computation

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish
Title of host publication37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020
EditorsChristophe Paul, Markus Blaser
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume154
ISBN (Electronic)9783959771405
DOIs
StatePublished - 2020
Event37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020 - Montpellier, France
Duration: 10 Mar 202013 Mar 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume154
ISSN (Print)1868-8969

Conference

Conference37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020
CountryFrance
CityMontpellier
Period10/03/2013/03/20

Keywords

  • BFS Trees
  • DFS Trees
  • Max-Leaf Spanning Trees

Fingerprint Dive into the research topics of 'Streaming complexity of spanning tree computation'. Together they form a unique fingerprint.

Cite this