An analysis of alternative strategies for implementing matching algorithms

DOI10.1002/NET.3230130406MaRDI QIDQ3668867zbMATHOpenAlexFDO

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)

• 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
• Balanced network flows. VII: Primal-dual algorithms.
• An efficient Dijkstra-like labeling method for computing shortest odd/even paths
• An efficient heuristic algorithm for minimum matching
• The symmetric travelling salesman problem. I: New fast lower bounds for the problem of optimal 2-matching
• 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
• Solving matching problems with linear programming
• 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
• Spanning cactus: complexity and extensions

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)