We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Robust Algorithms for the Stable Set Problem.
- Authors
Gerber, Michael U.; Lozin, Vadim V.
- 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.
- Subjects
ALGORITHMS; NP-complete problems; VERTEX operator algebras; CONVEX sets; GRAPHIC methods; COMBINATORIAL probabilities; GRAPH theory
- Publication
Graphs & Combinatorics, 2003, Vol 19, Issue 3, p347
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-002-0517-5