Implementation of O ( nm log n ) weighted matchings in general graphs

DOI10.1145/944618.944622zbMath1083.68650OpenAlexW2144856557MaRDI QIDQ5463431

Kurt Mehlhorn, Guido Schäfer

Publication date: 4 August 2005

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: http://www.jea.acm.org/2002/MehlhornMatching/

zbMATH Keywords

Edmonds' blossom-shrinking algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items

On matchings, T‐joins, and arc routing in road networks, A probability metrics approach for reducing the bias of optimality gap estimators in two-stage stochastic linear programming, Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems, A \(2/3\)-approximation algorithm for vertex-weighted matching, Computing in combinatorial optimization, Fast algorithms for the undirected negative cost cycle detection problem

Uses Software

• Blossom IV