Approximation algorithms for weighted matching

DOI10.1016/0304-3975(87)90022-3zbMATH Open0643.68084OpenAlexW1998129956MaRDI QIDQ1102118FDOQ1102118

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

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

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)

Cites Work

• Title not available (Why is that?)
• Applications of a Planar Separator Theorem
• Title not available (Why is that?)
• A Separator Theorem for Planar Graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• A separator theorem for graphs of bounded genus
• Title not available (Why is that?)
• On a Greedy Heuristic for Complete Matching
• Title not available (Why is that?)
• Title not available (Why is that?)

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
• Title not available (Why is that?)
• Weighted restricted 2-matching
• A new class of heuristic algorithms for weighted perfect matching
• Space-efficient approximation scheme for maximum matching in sparse graphs
• Weighted matching as a generic pruning technique applied to optimization constraints
• Title not available (Why is that?)
• Competitive weighted matching in transversal matroids
• Optimal Weighted Matchings for Rank-Deficient Sparse Matrices
• Approximating weighted matchings in parallel
• 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)