Robust Algorithms for the Stable Set Problem |
| |
Authors: | Michael U?Gerber Email author" target="_blank">Vadim V?LozinEmail author |
| |
Institution: | (1) Department of Mathematics, Swiss Federal Institute of Technology, CH-1015 Lausanne, Switzerland;(2) RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway, NJ 08854-8003, USA |
| |
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. |
| |
Keywords: | Stable set Stability number Polynomial algorithm |
本文献已被 SpringerLink 等数据库收录! |
|