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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
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