|
This article is cited in 5 scientific papers (total in 5 papers)
Complexity of some problems on hereditary classes of graphs
V. E. Alekseev, D. V. Korobitsyn
Abstract:
The independent set problem, the dominating set problem and the problem of the longest path are investigated for classes of graphs determined by finite sets of forbidden subgraphs. It is proved that if among the forbidden subgraphs there is a graph in which each connected component is homeomorphic to $K_2$ or to $K_{1,3}$, then each of these three problems is solved for graphs from such a class in polynomial time. If there are no such forbidden graphs, then all three problems remain $\rm{NP}$-hard.
Received: 28.06.1991
Citation:
V. E. Alekseev, D. V. Korobitsyn, “Complexity of some problems on hereditary classes of graphs”, Diskr. Mat., 4:4 (1992), 34–40
Linking options:
https://www.mathnet.ru/eng/dm760 https://www.mathnet.ru/eng/dm/v4/i4/p34
|
Statistics & downloads: |
Abstract page: | 566 | Full-text PDF : | 185 | First page: | 3 |
|