Improved linear time approximation algorithms for weighted matchings

DOI10.1007/B11961MaRDI QIDQ5900918zbMATH OpenOpenAlexFDO

Authors Doratha E. Drake, Stefan Hougardy

Publication date 26 May 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• A linear-time approximation algorithm for weighted matchings in graphs
• A simple approximation algorithm for the weighted matching problem
• scientific article; zbMATH DE number 1304326
• scientific article; zbMATH DE number 1982180
• Approximation algorithms for weighted matching

Cited in

(17)

• A simple approximation algorithm for the weighted matching problem
• Approximation algorithms for weighted matching
• A \(2/3\)-approximation algorithm for vertex-weighted matching
• A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
• Efficient matching for column intersection graphs
• A linear-time approximation algorithm for weighted matchings in graphs
• Near approximation of maximum weight matching through efficient weight reduction
• IMPROVED APPROXIMATION GUARANTEES FOR WEIGHTED MATCHING IN THE SEMI-STREAMING MODEL *
• Linear-time approximation for maximum weight matching
• A new class of heuristic algorithms for weighted perfect matching
• scientific article; zbMATH DE number 1304326 (Why is no real title available?)
• scientific article; zbMATH DE number 1982180 (Why is no real title available?)
• scientific article; zbMATH DE number 4116586 (Why is no real title available?)
• Engineering Algorithms for Approximate Weighted Matching
• An Improved Approximation Algorithm for the Matching Augmentation Problem
• Improved approximation algorithms for (1,2)-TSP and Max-TSP using path covers in the semi-streaming model
• Approximating weighted matchings in parallel

This page was built for publication: Improved linear time approximation algorithms for weighted matchings

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