Parallel approximation algorithms for maximum weighted matching in general graphs

DOI10.1016/S0020-0190(00)00128-9MaRDI QIDQ294847zbMATH OpenOpenAlexFDO

Authors Ryuhei Uehara, Zhi-Zhong Chen

Publication date 16 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019000001289?np=y

zbMATH Keywords

approximation algorithmsgraph algorithmsparallel algorithmsmaximum weighted matching

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1759463
• Approximating weighted matchings in parallel
• Approximating matchings in parallel
• A simple approximation algorithm for the weighted matching problem
• An efficient NC algorithm for approximate maximum weight matching

Cites work

• scientific article; zbMATH DE number 432790 (Why is no real title available?)
• scientific article; zbMATH DE number 1304326 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• scientific article; zbMATH DE number 1142309 (Why is no real title available?)
• scientific article; zbMATH DE number 1151367 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• A survey of heuristics for the weighted matching problem
• An improved parallel algorithm for maximal matching
• Approximating matchings in parallel
• Approximation algorithms for weighted matching
• Constructing a perfect matching is in random NC
• Efficient algorithms for finding maximum matching in graphs
• Paths, Trees, and Flowers
• The complexity of circuit value and network stability

Cited in

(12)

• Parallel graph algorithms for finding weighted matchings and subgraphs in computational science
• scientific article; zbMATH DE number 4087453 (Why is no real title available?)
• An efficient NC algorithm for approximate maximum weight matching
• scientific article; zbMATH DE number 1759463 (Why is no real title available?)
• Approximating matchings in parallel
• A parallel 2/3-approximation algorithm for vertex-weighted matching
• Sublinear estimation of weighted matchings in dynamic data streams
• An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs
• Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality
• On graph problems in a semi-streaming model
• Structural results on matching estimation with applications to streaming
• Approximating weighted matchings in parallel

This page was built for publication: Parallel approximation algorithms for maximum weighted matching in general graphs

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