Fast and Simple Algorithms for Weighted Perfect Matching

DOI10.1016/J.ENDM.2004.03.052MaRDI QIDQ3439168zbMATH OpenOpenAlexFDO

Authors Mirjam Wattenhofer, Roger Wattenhofer

Publication date 29 May 2007

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2004.03.052

zbMATH Keywords

approximation algorithmsweighted matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• A new class of heuristic algorithms for weighted perfect matching
• Experimental and Efficient Algorithms
• A linear-time approximation algorithm for weighted matchings in graphs
• A general class of heuristics for minimum weight perfect matching and fast special cases with doubly and triply logarithmic errors
• Faster scaling algorithms for general graph matching problems

Cites work

• scientific article; zbMATH DE number 432790 (Why is no real title available?)
• scientific article; zbMATH DE number 1305475 (Why is no real title available?)
• scientific article; zbMATH DE number 742977 (Why is no real title available?)
• Efficiency of a Good But Not Linear Set Union Algorithm
• Faster scaling algorithms for general graph matching problems
• On a Greedy Heuristic for Complete Matching
• Paths, Trees, and Flowers

Cited in

(16)

• Strong product of factor-critical graphs
• Fast profile matching algorithms - A survey
• Engineering Algorithms for Approximate Weighted Matching
• scientific article; zbMATH DE number 4116586 (Why is no real title available?)
• Computational comparison of several greedy algorithms for the minimum cost perfect matching problem on large graphs
• Scaling algorithms for weighted matching in general graphs
• A general class of heuristics for minimum weight perfect matching and fast special cases with doubly and triply logarithmic errors
• (1,2)-Hamiltonian completion on a matching
• A new class of heuristic algorithms for weighted perfect matching
• Experimental and Efficient Algorithms
• Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality
• Low weight perfect matchings
• Scaling algorithms for weighted matching in general graphs
• Faster scaling algorithms for general graph matching problems
• Fast algorithms for weighted myriad computation by fixed-point search
• Computing Minimum-Weight Perfect Matchings

This page was built for publication: Fast and Simple Algorithms for Weighted Perfect Matching

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