0

0

 Optimal per-edge processing times in the semi-streaming model
 摘  要: We present semi-streaming algorithms for basic graph problems that have optimal per-edge processing times and therefore surpass all previous semi-streaming algorithms for these tasks. The semi-streaming model, which is appropriate when dealing with massive graphs, forbids random access to the input and restricts the memory to O(n*polylog n) bits. Particularly, the formerly best per-edge processing times for finding the connected components and a bipartition are O(alpha(n)), for determining k-vertex and k-edge connectivity O(k^2n) and O(n*log n) respectively for any constant k and for computing a minimum spanning forest O(log n). All these time bounds we reduce to O(1). Every presented algorithm determines a solution asymptotically as fast as the best corresponding algorithm up to date in the classical RAM model, which therefore cannot convert the advantage of unlimited memory and random access into superior computing times for these problems.
 发  表:

 论文统计图 .axis path, .axis line { fill: none; stroke: #000; shape-rendering: crispEdges; } .line { fill: none; stroke-width: 1.5px; }
 共享有6个版本  [展开全部版本] [收起版本] http://arxiv.org/abs/0708.4284 http://dx.doi.org/10.1016/j.ipl.2007.06.004 http://linkinghub.elsevier.com/retrieve/pii/S0020019007001512
 Bibtex @article{ author = {Mariano Zelke}, title = {Optimal Per-Edge Processing Times in the Semi-Streaming Model}, journal = {Information Processing Letters}, volume = {104}, year = {2007}, pages = {106--112}, issue = {3}, doi = {10.1016/j.ipl.2007.06.004} }

 还没有人点评哦

 Weighted Matching in the Semi-Streaming Model Recognizing well-parenthesized expressions in the streaming model Streaming algorithm for graph spanners - single pass and constant processing time per edge Graph Sparsification in the Semi-streaming Model Acyclic edge colourings of graphs with the number of edges linearly bounded by the number of vertices A near-optimal algorithm for computing the entropy of a stream On acyclic edge coloring of toroidal graphs Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners Graph Distances in the Data-Stream Model Bipartite Graph Matchings in the Semi-streaming Model