Abstract.
The stable set problem is to find in a simple graph a maximum subset of pairwise non-adjacent vertices. The problem is known to be NP-hard in general and can be solved in polynomial time on some special classes, like cographs or claw-free graphs. Usually, efficient algorithms assume membership of a given graph in a special class. Robust algorithms apply to any graph G and either solve the problem for G or find in it special forbidden configurations. In the present paper we describe several efficient robust algorithms, extending some known results.
We’re sorry, something doesn't seem to be working properly.
Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.
Author information
Authors and Affiliations
Corresponding author
About this article
Cite this article
Gerber, M., Lozin, V. Robust Algorithms for the Stable Set Problem. Graphs and Combinatorics 19, 347–356 (2003). https://doi.org/10.1007/s00373-002-0517-5
Received:
Issue Date:
DOI: https://doi.org/10.1007/s00373-002-0517-5