Maintaining approximate maximum weighted matching in fully dynamic graphs

DOI10.4230/LIPICS.FSTTCS.2012.257MaRDI QIDQ2957502zbMATH OpenFDO

Authors Abhash Anand, Surender Baswana, Manoj Gupta, Sandeep Sen

Publication date 26 January 2017

Full work available at URL https://arxiv.org/abs/1207.3976

zbMATH Keywords

dynamic algorithmgraph algorithmmatching

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Recommendations

• Fully dynamic maximal matching in O( n) update time
• Fully dynamic maximal matching in O( n) update time (corrected version)
• Maintaining approximate maximum matching in an incremental bipartite graph in polylogarithmic update time
• Fully dynamic matching in bipartite graphs
• New deterministic approximation algorithms for fully dynamic matching

Cited in

(7)

• Maintaining approximate maximum matching in an incremental bipartite graph in polylogarithmic update time
• Dynamic Matchings in Left Weighted Convex Bipartite Graphs
• scientific article; zbMATH DE number 6866348 (Why is no real title available?)
• Fully dynamic maximal matching in O( n) update time (corrected version)
• Fully dynamic maximal matching in O( n) update time
• A Batch-dynamic Suitor Algorithm for Approximating Maximum Weighted Matching
• Dynamic algorithms for submodular matching

This page was built for publication: Maintaining approximate maximum weighted matching in fully dynamic graphs

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