|
Diskretnyi Analiz i Issledovanie Operatsii, 2012, Volume 19, Issue 4, Pages 66–72
(Mi da698)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Polynomial solvability of the independent set problem for one class of graphs with small diameter
D. S. Malyshevab a Nizhniy Novgorod Higher School of Economics, Nizhniy Novgorod, Russia
b Nizhniy Novgorod State University, Nizhniy Novgorod, Russia
Abstract:
A constructive approach to forming new cases in the family of hereditary parts of the set ${\mathcal Free}(\{P_5,C_5\})$ with polynomial-time solvability of the independent set problem is considered. We prove that if this problem is polynomial-time solvable in the class ${\mathcal Free}(\{P_5,C_5,G\})$ then for any graph $H$ which can inductively be obtained from $G$ by means of applying addition with $K_1$ or multiplication by $K_1$ to the graph $G$ the problem has the same computational status in ${\mathcal Free}(\{P_5,C_5,H\})$. Bibliogr. 10.
Keywords:
the independent set problem, computational complexity, polynomial algorithm.
Received: 19.10.2011
Citation:
D. S. Malyshev, “Polynomial solvability of the independent set problem for one class of graphs with small diameter”, Diskretn. Anal. Issled. Oper., 19:4 (2012), 66–72
Linking options:
https://www.mathnet.ru/eng/da698 https://www.mathnet.ru/eng/da/v19/i4/p66
|
Statistics & downloads: |
Abstract page: | 315 | Full-text PDF : | 79 | References: | 45 | First page: | 6 |
|