LIPIcs.STACS.2008.1312.pdf
- Filesize: 175 kB
- 12 pages
Document
Weighted Matching in the Semi-Streaming Model
Author
-
Part of:
Volume:
25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NoDerivs 3.0 Unported license
- Publication Date: 2008-02-06
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
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)
0PDF Downloads