Acta Mathematica Vietnamica
- Volume 49
- Volume 48
- Volume 47
- Volume 46
- Volume 45
- Volume 44
- Volume 43
- Volume 42
- Volume 41
- Volume 40
- Volume 39
- Volume 38
- Volume 37
- Volume 36
- Volume 35
- Volume 34
- Volume 33
- Volume 32
- Volume 31
- Volume 30
- Volume 29
- Volume 28
- Volume 27
- Volume 26
- Volume 25
- Volume 24
- Volume 23
- Volume 22
- Volume 21
- Volume 20
- Volume 19
- Volume 18
- Volume 17
- Volume 16
- Volume 15
- Volume 14
- Volume 13
- Volume 12
- Volume 11
- Volume 10
- Volume 9
- Volume 8
- Volume 7
- Volume 6
- Volume 5
- Volume 4
- Volume 3
- Volume 2
- Volume 1
On the Maximum Independent Set Problem in Graphs of Bounded Maximum Degree
Ngoc C. Lê
,
Trung Tran
Abstract
We consider the maximum independent set (MIS) problem, i.e., the problem asking for a vertex subset of maximum cardinality of a graph such that no two vertices in this set are adjacent. The problem is known to be NP-hard in general, even if restricted on graphs of maximum degree at most $\Delta$ for a given integer $\Delta\ge 3$, i.e., every vertex is of degree at most $\Delta$. We try to figure out some bounded maximum degree graph classes, under which the problem can be solved in polynomial time.