Weighted Matching in the Semi-Streaming Model

Details Weighted Matching in the Semi-Streaming Model Weighted Matching in the Semi-Streaming Model

2007-09-21

arxiv.org/abs/0709.3384v1

Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (2008)

Computer Science

Discrete Mathematics

12 pages, 2 figures

Scientific paper

We reduce the best known approximation ratio for finding a weighted matching
of a graph using a one-pass semi-streaming algorithm from 5.828 to 5.585. The
semi-streaming model forbids random access to the input and restricts the
memory to O(n*polylog(n)) bits. It was introduced by Muthukrishnan in 2003 and
is appropriate when dealing with massive graphs.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-256579