A note on the approximation of a minimum-weight maximal independent set
From MaRDI portal
Publication:1303785
DOI10.1023/A:1008765214400zbMath0958.90093OpenAlexW1509309803MaRDI QIDQ1303785
Publication date: 9 April 2001
Published in: Computational Optimization and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1023/a:1008765214400
computational complexitycombinatorial problemindependent setpolynomial-time approximation algorithms
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)
Related Items (4)
Computing the largest bond and the maximum connected cut of a graph ⋮ Independent sets in graphs ⋮ On the inapproximability of independent domination in \(2P_3\)-free perfect graphs ⋮ (In)approximability of maximum minimal FVS
This page was built for publication: A note on the approximation of a minimum-weight maximal independent set
