Parallel approximation algorithms for maximum weighted matching in general graphs

DOI10.1016/S0020-0190(00)00128-9zbMATH Open1339.05406OpenAlexW2023492687MaRDI QIDQ294847FDOQ294847

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

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

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)

Cites Work

• Paths, Trees, and Flowers
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Constructing a perfect matching is in random NC
• Title not available (Why is that?)
• An improved parallel algorithm for maximal matching
• Approximation algorithms for weighted matching
• The complexity of circuit value and network stability
• Approximating matchings in parallel
• A survey of heuristics for the weighted matching problem
• Efficient algorithms for finding maximum matching in graphs
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (10)

• On graph problems in a semi-streaming model
• Parallel graph algorithms for finding weighted matchings and subgraphs in computational science
• An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs
• Sublinear estimation of weighted matchings in dynamic data streams
• Structural results on matching estimation with applications to streaming
• Approximating matchings in parallel
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximating weighted matchings in parallel
• An efficient NC algorithm for approximate maximum weight matching

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)