𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The Approximability Behaviour of Some Combinatorial Problems with Respect to the Approximability of a Class of Maximum Independent Set Problems

✍ Scribed by Marc Demange; Vangelis Th. Paschos

Book ID
110265860
Publisher
Springer US
Year
1997
Tongue
English
Weight
180 KB
Volume
7
Category
Article
ISSN
0926-6003

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On easy and hard hereditary classes of g
On easy and hard hereditary classes of graphs with respect to the independent set problem
✍ Vladimir E. Alekseev πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 162 KB

In this paper we introduce the concept of a boundary class, which is a helpful tool for classiΓΏcation of hereditary classes of graphs according to the complexity of the independent set problem. It is shown that in a class X deΓΏned by a ΓΏnite set of forbidden induced subgraphs, the problem is NP-hard