Weighted Matching in the Semi-Streaming Model

Author Mariano Zelke



PDF
Thumbnail PDF

File

LIPIcs.STACS.2008.1312.pdf
  • Filesize: 175 kB
  • 12 pages

Document Identifiers

Author Details

Mariano Zelke

Cite AsGet BibTex

Mariano Zelke. Weighted Matching in the Semi-Streaming Model. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 669-680, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.STACS.2008.1312

Abstract

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 $mathcal{O(ncdotmbox{polylog,n)$ bits. It was introduced by Muthukrishnan in 2003 and is appropriate when dealing with massive graphs.
Keywords
  • Semi-streaming algorithm
  • matching
  • approximation algorithm
  • graph algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail