An analysis of alternative strategies for implementing matching algorithms

DOI10.1002/NET.3230130406zbMATH Open0519.68055OpenAlexW2007214900MaRDI QIDQ3668867FDOQ3668867

Authors: Michael O. Ball, Ulrich Derigs 

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)

Cites Work

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

Cited In (12)

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

This page was built for publication: An analysis of alternative strategies for implementing matching algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3668867)