scientific article; zbMATH DE number 6866348

DOI10.4230/LIPIcs.ITCS.2017.58zbMath1404.68088MaRDI QIDQ4638113

No author found.

Publication date: 3 May 2018

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

maximum matchingdynamic algorithmsmaximum weight matchingdynamic graphs

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) Signed and weighted graphs (05C22)

Related Items

Fast primal-dual update against local weight update in linear assignment problem and its application ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum weight bipartite matching in matrix multiplication time
• Matching is as easy as matrix inversion
• Maintaining a large matching and a small vertex cover
• Maximum matchings in general graphs through randomization
• Fully Dynamic Matching in Bipartite Graphs
• Powers of tensors and fast matrix multiplication
• Faster scaling algorithms for general graph matching problems
• Faster Fully Dynamic Matchings with Small Approximation Ratios
• Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
• New deterministic approximation algorithms for fully dynamic matching
• Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
• An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
• Multiplying matrices faster than coppersmith-winograd
• Algorithms – ESA 2004
• Fully Dynamic Maximal Matching in O (log n) Update Time
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs