๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Planar graph classes with the independent set problem solvable in polynomial time

โœ Scribed by V. E. Alekseev; D. S. Malyshev


Book ID
111471204
Publisher
Pleiades Publishing
Year
2009
Tongue
English
Weight
469 KB
Volume
3
Category
Article
ISSN
1990-4789

No coin nor oath required. For personal study only.


๐Ÿ“œ SIMILAR VOLUMES


On easy and hard hereditary classes of g
โœ 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