Maximum matching on trees in the online preemptive and the incremental graph models

DOI10.1007/s00453-019-00593-6zbMath1434.68372OpenAlexW2951788872MaRDI QIDQ2329370

Sumedh Tirodkar, Sundar Vishwanathan

Publication date: 17 October 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-019-00593-6

zbMATH Keywords

primal-dual analysisincremental dynamic graph modelonline preemptive model

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Cites Work

• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On graph problems in a semi-streaming model
• Improved Bounds for Online Preemptive Matching
• Maintaining Approximate Maximum Matching in an Incremental Bipartite Graph in Polylogarithmic Update Time
• Buyback Problem - Approximate Matroid Intersection with Cancellation Costs
• Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model
• On Randomized Algorithms for Matching in the Online Preemptive Model
• Faster Fully Dynamic Matchings with Small Approximation Ratios
• Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log³ n) Worst Case Update Time
• Online Weighted Matching
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

This page was built for publication: Maximum matching on trees in the online preemptive and the incremental graph models