Weighted matching in the semi-streaming model

DOI10.1007/s00453-010-9438-5zbMath1246.68266OpenAlexW1498807656MaRDI QIDQ2428674

Mariano Zelke

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2008/1312/

zbMATH Keywords

matchinggraph algorithmapproximation algorithmsemi-streaming algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items

Sublinear Estimation of Weighted Matchings in Dynamic Data Streams ⋮ Maximum Matching in Turnstile Streams ⋮ Superlinear lower bounds for multipass graph processing ⋮ Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model ⋮ Improved bounds for randomized preemptive online matching ⋮ Communication complexity of approximate maximum matching in the message-passing model ⋮ A simple augmentation method for matchings with applications to streaming algorithms ⋮ Structural results on matching estimation with applications to streaming ⋮ The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quality matching and local improvement for multilevel graph-partitioning
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complexity and modeling aspects of mesh refinement into quadrilaterals
• Optimal per-edge processing times in the semi-streaming model
• A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
• A linear-time approximation algorithm for weighted matchings in graphs
• IMPROVED APPROXIMATION GUARANTEES FOR WEIGHTED MATCHING IN THE SEMI-STREAMING MODEL *
• Automata, Languages and Programming
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques