𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Parameterized complexity of the maximum independent set problem and the speed of hereditary properties

✍ Scribed by Vadim V. Lozin

Book ID
108120703
Publisher
Elsevier Science
Year
2009
Tongue
English
Weight
185 KB
Volume
34
Category
Article
ISSN
1571-0653

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The structure and maximum number of maxi
The structure and maximum number of maximum independent sets in trees
✍ Jennifer Zito πŸ“‚ Article πŸ“… 1991 πŸ› John Wiley and Sons 🌐 English βš– 732 KB

A subset of vertices is a maximum independent set if no two of the vertices are joined by an edge and the subset has maximum cardinality. In this paper we answer a question posed by Herb Wilf. We show that the greatest number of maximum independent sets for a tree of n vertices is 2(n-3\* for odd n

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