AN EFFICIENT NC ALGORITHM FOR APPROXIMATE MAXIMUM WEIGHT MATCHING

DOI10.1142/S1793830913500134zbMath1276.68174OpenAlexW2143780628MaRDI QIDQ2864855

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

graph algorithmsapproximation algorithmsmaximum weight matchingNC algorithms

Mathematics Subject Classification ID

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

Cites Work

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

This page was built for publication: AN EFFICIENT NC ALGORITHM FOR APPROXIMATE MAXIMUM WEIGHT MATCHING