scientific article; zbMATH DE number 6866348

DOI10.4230/LIPICS.ITCS.2017.58MaRDI QIDQ4638113zbMATH OpenFDO

Authors

Publication date 3 May 2018

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2017.58

zbMATH Keywords

dynamic algorithmsdynamic graphsmaximum matchingmaximum weight matching

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• A framework for dynamic matching in weighted graphs
• scientific article; zbMATH DE number 4062556
• Approximation algorithms for weighted matching
• Distributed Weighted Matching
• A note on weighted distributed match-making
• Maintaining approximate maximum weighted matching in fully dynamic graphs
• A generalized hypergreedy algorithm for weighted perfect matching
• Approximating weighted induced matchings
• Dynamic Matching Algorithms in Practice

Cites work

• Algorithms – ESA 2004
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
• Deterministic fully dynamic data structures for vertex cover and matching
• Faster dynamic matchings and vertex connectivity
• Faster fully dynamic matchings with small approximation ratios
• Faster scaling algorithms for general graph matching problems
• Fully dynamic matching in bipartite graphs
• Fully Dynamic Maximal Matching in O (log n) Update Time
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• Improved streaming algorithms for weighted matching, via unweighted matching
• Maintaining a large matching and a small vertex cover
• Maintaining approximate maximum weighted matching in fully dynamic graphs
• Matching is as easy as matrix inversion
• Maximum matchings in general graphs through randomization
• Maximum weight bipartite matching in matrix multiplication time
• Multiplying matrices faster than coppersmith-winograd
• New deterministic approximation algorithms for fully dynamic matching
• Powers of tensors and fast matrix multiplication

Cited in

(6)

• A simple reduction from maximum weight matching to maximum cardinality matching
• Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
• Fast primal-dual update against local weight update in linear assignment problem and its application
• A Batch-dynamic Suitor Algorithm for Approximating Maximum Weighted Matching
• Decremental matching in general weighted graphs
• Dynamic algorithms for submodular matching

This page was built for publication:

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