k-Connectivity in the Semi-Streaming Model

Computer Science – Discrete Mathematics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

13 pages, submitted to Theoretical Computer Science

Scientific paper

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(k^2*n) to process each input edge. The second algorithm reads the input k+1 times and needs time O(k+alpha(n)) per input edge. Using its constructed subgraph the second algorithm can also generate all l-separators of the input graph for all l

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

k-Connectivity 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 k-Connectivity in the Semi-Streaming Model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and k-Connectivity in the Semi-Streaming Model will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-219930

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.