Approximation algorithms for weighted matching

DOI10.1016/0304-3975(87)90022-3MaRDI QIDQ1102118zbMATH OpenOpenAlexFDO

Authors Shankar M. Venkatesan

Publication date 1987

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(87)90022-3

zbMATH Keywords

weighted matchingApproximation algorithms

Mathematics Subject Classification ID

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

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3965443 (Why is no real title available?)
• scientific article; zbMATH DE number 3752239 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3314878 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• A separator theorem for graphs of bounded genus
• Applications of a Planar Separator Theorem
• On a Greedy Heuristic for Complete Matching
• The Rectilinear Steiner Tree Problem is $NP$-Complete

Cited in

(17)

• Solving various weighted matching problems with constraints
• Approximate Matching in Weighted Sequences
• An algorithm for weighted fractional matroid matching
• Parallel approximation algorithms for maximum weighted matching in general graphs
• New approximation results on graph matching and related problems
• Improved linear time approximation algorithms for weighted matchings
• scientific article; zbMATH DE number 6866348 (Why is no real title available?)
• Weighted restricted 2-matching
• A new class of heuristic algorithms for weighted perfect matching
• Weighted matching as a generic pruning technique applied to optimization constraints
• Space-efficient approximation scheme for maximum matching in sparse graphs
• scientific article; zbMATH DE number 1759463 (Why is no real title available?)
• Competitive weighted matching in transversal matroids
• Approximating weighted matchings in parallel
• Optimal Weighted Matchings for Rank-Deficient Sparse Matrices
• An efficient NC algorithm for approximate maximum weight matching
• Exact algorithms for minimum weighted dominating induced matching

This page was built for publication: Approximation algorithms for weighted matching

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