An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs

DOI10.1145/321941.321942zbMath0327.05121OpenAlexW2090168101WikidataQ56626058 ScholiaQ56626058MaRDI QIDQ4091992

Publication date: 1976

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321941.321942

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (05C99) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items

ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH, Probabilistic analysis of divide‐and‐conquer heuristics for minimum weighted euclidean matching, An augmenting path algorithm for linear matroid parity, Gallai-Edmonds decomposition as a pruning technique, Approximation algorithms for hard capacitated \(k\)-facility location problems, Improved Approximation Algorithms for Weighted 2-Path Partitions, Complexity results for storage loading problems with stacking constraints, Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers, Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem, Attribute value reordering for efficient hybrid OLAP, The general maximum matching algorithm of Micali and Vazirani, Two dimensional maximum weight matching using Manhattan topology, Incremental assignment problem, Improved approximations for capacitated vehicle routing with unsplittable client demands, Strict matching matroids and matroid algorithms, Approximation algorithms for maximum dispersion, Worst-case greedy matchings in the unitd-cube, A generalized Hungarian method for solving minimum weight perfect matching problems with algebraic objective, A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints, F-factors of graphs: A generalized matching problem, On vertex independence number of uniform hypergraphs, A weight-scaling algorithm for \(f\)-factors of multigraphs, A quantization framework for smoothed analysis of Euclidean optimization problems, On the parallel complexity of constrained read-once refutations in UTVPI constraint systems, On generalized matching problems, New approximation results on graph matching and related problems, Deep Haar scattering networks, Algorithmic proofs of two relations between connectivity and the 1- factors of a graph, Partitioning planar graphs: a fast combinatorial approach for max-cut, A two-stage hardware scheduler combining greedy and optimal scheduling, An efficient distributed algorithm for maximum matching in general graphs, Reinforcement learning for optimal error correction of toric codes, Constraint programming approach for school timetabling., A model for minimizing active processor time, 1-Approximation algorithm for bottleneck disjoint path matching, Greedy matching: guarantees and limitations, Matching theory -- a sampler: From Dénes König to the present, Dynamic matchings and quasidynamic fractional matchings. I, Linear algorithms for testing the sign stability of a matrix and for finding Z-maximum matchings in acyclic graphs, Combined bus and driver scheduling, On the anti-Kekulé problem of cubic graphs, The labeled maximum matching problem, A randomized approximation algorithm for metric triangle packing, Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem, Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs, Searching for a strong double tracing in a graph, Trustworthy Graph Algorithms (Invited Talk), Stacks in canonical RNA pseudoknot structures, Approximate minimum weight matching on points in k-dimensional space, Minimal length test vectors for multiple-fault detection, Maximum matching of given weight in complete and complete bipartite graphs, Optimum matching forests I: Special weights, Algorithms for Weighted Matching Generalizations II: f-factors and the Special Case of Shortest Paths, Unnamed Item, Unnamed Item, A linear-time algorithm for a special case of disjoint set union, Computing maximum non-crossing matching in convex bipartite graphs, A complexity and approximation framework for the maximization scaffolding problem, A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm, Scheduling jobs to two machines subject to batch arrival ordering