0

0

 k-Connectivity in the Semi-Streaming Model
 摘  要: We present the first semi-streaming algorithms to determine k-connectivity of an undirected graph with k being any constant. The semi-streaming model for graph algorithms was introduced by Muthukrishnan in 2003 and turns out to be useful when dealing with massive graphs streamed in from an external storage device. Our two semi-streaming algorithms each compute a sparse subgraph of an input graph G and can use this subgraph in a postprocessing step to decide k-connectivity of G. To this end the first algorithm reads the input stream only once and uses time O(k2n) to process each input edge. The second algorithm reads the input k +1 times and needs time O(k +�(n)) per input edge. Using its constructed subgraph the second algorithm can also generate all l-separators of the input graph for all l < k.
 发  表:

 论文统计图 .axis path, .axis line { fill: none; stroke: #000; shape-rendering: crispEdges; } .line { fill: none; stroke-width: 1.5px; }
 共享有7个版本  [展开全部版本] [收起版本] /viewdoc/redirect;jsessionid=9E016FBB25AD5A76E5AB8A552BBB06B2?doi=10.1.1.342.1401&label=DBLP http://arxiv.org/abs/cs/0608066 http://arxiv.org/pdf/cs/0608066v1.pdf
 Bibtex @MISC{author = {Mariano Zelke},title = {k-connectivity in the semi-streaming model},year = {2006}}

 还没有人点评哦

 Adapting Parallel Algorithms to the W-Stream Model, with Applications to Graph Problems Streaming Graph Computations with a Helpful Advisor Weighted Matching in the Semi-Streaming Model Bounds for Compression in Streaming Models Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments Graph Sparsification in the Semi-streaming Model Optimal per-edge processing times in the semi-streaming model Weighted Matching in the Semi-Streaming Model Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners Graph Distances in the Data-Stream Model