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

DOI10.1007/S00453-019-00593-6MaRDI QIDQ2329370zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Maximum matching on trees in the online preemptive and the incremental dynamic graph models
• On randomized algorithms for matching in the online preemptive model
• Improved bounds for randomized preemptive online matching
• Improved bounds for online preemptive matching
• Online algorithms for maximum cardinality matching with edge arrivals

Cites work

• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Buyback problem -- approximate matroid intersection with cancellation costs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Faster fully dynamic matchings with small approximation ratios
• Fully dynamic approximate maximum matching and minimum vertex cover in \(O(\log^3 n)\) worst case update time
• Improved approximation guarantees for weighted matching in the semi-streaming model
• Improved bounds for online preemptive matching
• Maintaining approximate maximum matching in an incremental bipartite graph in polylogarithmic update time
• On graph problems in a semi-streaming model
• On randomized algorithms for matching in the online preemptive model
• Online Weighted Matching

Cited in

(6)

• Shortest augmenting paths for online matchings on trees
• Improved bounds for randomized preemptive online matching
• Online algorithms for maximum cardinality matching with edge arrivals
• Improved bounds for online preemptive matching
• On randomized algorithms for matching in the online preemptive model
• Maximum matching on trees in the online preemptive and the incremental dynamic graph models

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2329370)