An efficient NC algorithm for approximate maximum weight matching

DOI10.1142/S1793830913500134MaRDI QIDQ2864855zbMATH OpenOpenAlexFDO

Authors Satyajit Banerjee

Publication date 26 November 2013

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s1793830913500134

zbMATH Keywords

approximation algorithmsgraph algorithmsmaximum weight matchingNC algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• A fast and efficient NC algorithm for maximal matching
• Near approximation of maximum weight matching through efficient weight reduction
• NC algorithms for weighted planar perfect matching and related problems
• Linear-time approximation for maximum weight matching
• Publication:3487421
• Approximation algorithms for weighted matching
• A simple approximation algorithm for the weighted matching problem
• New algorithms for maximum weight matching and a decomposition theorem
• Efficient approximation algorithms for weighted \(b\)-matching

Cites work

• Approximating weighted matchings in parallel
• Constructing a Maximal Independent Set in Parallel
• Parallel approximation algorithms for maximum weighted matching in general graphs

Cited in

(3)

• Parallel approximation algorithms for maximum weighted matching in general graphs
• scientific article; zbMATH DE number 1759463 (Why is no real title available?)
• Approximating weighted matchings in parallel

This page was built for publication: An efficient NC algorithm for approximate maximum weight matching

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