𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Approximation Properties of the Independent Set Problem for Low Degree Graphs

✍ Scribed by P. Berman; T. Fujito

Book ID
105915311
Publisher
Springer
Year
1999
Tongue
English
Weight
160 KB
Volume
32
Category
Article
ISSN
1433-0490

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the nonseparating independent set pro
On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
✍ Shuichi Ueno; Yoji Kajitani; Shin'ya Gotoh πŸ“‚ Article πŸ“… 1988 πŸ› Elsevier Science 🌐 English βš– 350 KB

This paper shows that both the nonseparating independent set problem and feedback set problem can be solved in polynomial time for graphs with no vertex degree exceeding 3 by reducing the problems to the matroid parity problem.

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