Maximum matching on trees in the online preemptive and the incremental graph models
DOI10.1007/S00453-019-00593-6zbMATH Open1434.68372OpenAlexW2951788872MaRDI QIDQ2329370FDOQ2329370
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
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
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)
Cites Work
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On graph problems in a semi-streaming model
- Improved approximation guarantees for weighted matching in the semi-streaming model
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Online Weighted Matching
- On randomized algorithms for matching in the online preemptive model
- Buyback problem -- approximate matroid intersection with cancellation costs
- Improved bounds for online preemptive matching
- 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
- Maintaining approximate maximum matching in an incremental bipartite graph in polylogarithmic update time
Cited In (6)
- Shortest augmenting paths for online matchings on trees
- Online algorithms for maximum cardinality matching with edge arrivals
- Improved bounds for randomized preemptive online matching
- 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)
