An analysis of alternative strategies for implementing matching algorithms

DOI10.1002/net.3230130406zbMath0519.68055OpenAlexW2007214900MaRDI QIDQ3668867

Ulrich Derigs, Michael O. Ball

Publication date: 1983

Published in: Networks (Search for Journal in Brave)

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

zbMATH Keywords

undirected graphweighted matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Solving matching problems with linear programming, The symmetric travelling salesman problem. I: New fast lower bounds for the problem of optimal 2-matching, An efficient heuristic algorithm for minimum matching, Spanning cactus: complexity and extensions, An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs, Weighted matching as a generic pruning technique applied to optimization constraints, Balanced network flows. VII. Primal-dual algorithms, HIGH QUALITY QUADRILATERAL SURFACE MESHING WITHOUT TEMPLATE RESTRICTIONS: A NEW APPROACH BASED ON NETWORK FLOW TECHNIQUES, Blossom V: A new implementation of a minimum cost perfect matching algorithm, A vehicle routing improvement algorithm comparison of a greedy and a matching implementation for inventory routing, On the hierarchical Chinese postman problem with linear ordered classes, An efficient Dijkstra-like labeling method for computing shortest odd/even paths

Cites Work

• Optimal set partitioning, matchings and lagrangian duality
• Maximum matching and a polyhedron with 0,1-vertices