Boundary graph classes for some maximum induced subgraph problems
被引:0
|
作者:
Dmitriy S. Malyshev
论文数: 0引用数: 0
h-index: 0
机构:National Research University Higher School of Economics,Department of Mathematical Logic and Higher Algebra
Dmitriy S. Malyshev
机构:
[1] National Research University Higher School of Economics,Department of Mathematical Logic and Higher Algebra
[2] National Research University of Nizhny Novgorod,undefined
来源:
Journal of Combinatorial Optimization
|
2014年
/
27卷
关键词:
Computational complexity;
Boundary graph class;
Maximum induced subgraph problem;
D O I:
暂无
中图分类号:
学科分类号:
摘要:
The notion of a boundary graph class was recently introduced for a classification of hereditary graph classes according to the complexity of a considered problem. Two concrete graph classes are known to be boundary for several graph problems. We formulate a criterion to determine whether these classes are boundary for a given graph problem or not. We also demonstrate that the classes are simultaneously boundary for some continuous set of graph problems and they are not simultaneously boundary for another set of the same cardinality. Both families of problems are constituted by variants of the maximum induced subgraph problem.