New primal and dual matching heuristics

DOI10.1007/BF01293485zbMath0827.68047OpenAlexW2077074857MaRDI QIDQ1891231

Michael Jünger, William R. Pulleyblank

Publication date: 30 May 1995

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01293485

zbMATH Keywords

heuristicminimum-cost spanning treemoat widths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (4)

An asymptotic theory for recurrence relations based on minimization and maximization. ⋮ A linear programming approach to increasing the weight of all minimum spanning trees ⋮ Separating from the dominant of the spanning tree polytope ⋮ Network reinforcement

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower bound to the complexity of Euclidean and rectilinear matching algorithms
• Computing correct Delaunay triangulations
• IMPROVEMENTS OF THE INCREMENTAL METHOD FOR THE VORONOI DIAGRAM WITH COMPUTATIONAL COMPARISON OF VARIOUS ALGORITHMS
• A survey of heuristics for the weighted matching problem
• Solving matching problems with linear programming
• Euclidean matching problems and the metropolis algorithm
• Solving large-scale matching problems efficiently: A new primal matching approach
• A new class of heuristic algorithms for weighted perfect matching
• On a Greedy Heuristic for Complete Matching
• Heuristics for planar minimum‐weight perfect metchings
• Tight bounds for christofides' traveling salesman heuristic
• Optimal control of plotting and drilling machines: A case study
• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices

This page was built for publication: New primal and dual matching heuristics