Optimal Per-Edge Processing Times in the Semi-Streaming Model

Details Optimal Per-Edge Processing Times in the Semi-Streaming Model Optimal Per-Edge Processing Times in the Semi-Streaming Model

2007-08-31

arxiv.org/abs/0708.4284v1

Information Processing Letters, Volume 104, Issue 3, 2007, Pages 106-112

Computer Science

Discrete Mathematics

8 pages, 1 table

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Optimal Per-Edge Processing Times in the Semi-Streaming Model does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Per-Edge Processing Times in the Semi-Streaming Model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Per-Edge Processing Times in the Semi-Streaming Model will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-617966