An $O(EV\log V)$ Algorithm for Finding a Maximal Weighted Matching in General Graphs
From MaRDI portal
Publication:3718168
DOI10.1137/0215009zbMath0589.68050OpenAlexW2040326319MaRDI QIDQ3718168
Harold N. Gabow, Silvio Micali, Zvi Galil
Publication date: 1986
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0215009
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (22)
Euclidean maximum matchings in the plane -- local to global ⋮ Blossom-Quad: A non-uniform quadrilateral mesh generator using a minimum-cost perfect-matching algorithm ⋮ Minimum weight euclidean matching and weighted relative neighborhood graphs ⋮ Linear-Time Approximation for Maximum Weight Matching ⋮ THE MAXIMUM WEIGHT PERFECT MATCHING PROBLEM FOR COMPLETE WEIGHTED GRAPHS IS IN PC∗† ⋮ A weight-scaling algorithm for \(f\)-factors of multigraphs ⋮ A framework for automated distributed implementation of component-based models ⋮ A simple reduction from maximum weight matching to maximum cardinality matching ⋮ Improved complexity bounds for location problems on the real line ⋮ Dynamic Matching Algorithms in Practice ⋮ Weighted matching as a generic pruning technique applied to optimization constraints ⋮ 1-Approximation algorithm for bottleneck disjoint path matching ⋮ Walrasian equilibrium: Hardness, approximations and tractable instances ⋮ Using quadratic programming to solve high multiplicity scheduling problems on parallel machines ⋮ An algorithm for min-cost edge-disjoint cycles and its applications ⋮ Blossom V: A new implementation of a minimum cost perfect matching algorithm ⋮ On sum coloring of graphs ⋮ A genetic-based framework for solving (multi-criteria) weighted matching problems. ⋮ Maximum colored trees in edge-colored graphs ⋮ An Adaptive Multigrid Method Based on Path Cover ⋮ Unnamed Item ⋮ Fast algorithms for the undirected negative cost cycle detection problem
This page was built for publication: An $O(EV\log V)$ Algorithm for Finding a Maximal Weighted Matching in General Graphs
