A shortest augmenting path method for solving minimal perfect matching problems

DOI10.1002/net.3230110407zbMath0475.05069OpenAlexW2058494699MaRDI QIDQ3931440

Ulrich Derigs

Publication date: 1981

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230110407

zbMATH Keywords

matchingshortest augmenting paths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

\textsc{Laps}\ \textsc{Care} -- an operational system for staff planning of home care, An efficient matching algorithm applied in statistical physics, Algorithms for finding k-best perfect matchings, A computational study of efficient shortest path algorithms, Matching problems with generalized upper bound side constraints, Travelling salesman problem tools for microcomputers, How to find Steiner minimal trees in Euclidean \(d\)-space, Some concepts of stability analysis in combinatorial optimization, Aircrew schedule generation using repeated matching, Unnamed Item, On the use of optimal fractional matchings for solving the (integer) matching problem, An efficient algorithm for the bipartite matching problem, Microcomputer-based algorithms for large scale shortest path problems, An efficient Dijkstra-like labeling method for computing shortest odd/even paths, A repeated matching heuristic for the single-source capacitated facility location problem

Cites Work

• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices
• Unnamed Item