Critical elements in combinatorially closed families of graph classes
D. S. Malyshevab
a Lobachevsky State University,
23 Gagarin Ave., 603950 Nizhny Novgorod, Russia
b National Research University Higher School of Economics,
25/12 Bolshaya Pecherskaya St., 603155 Nizhny Novgorod, Russia
The notions of boundary and minimal hard classes of graphs, united by the term “critical classes”, are useful tools for analysis of computational complexity of graph problems in the family of hereditary graph classes. In this family, boundary classes are known for several graph problems. In the paper, we consider critical graph classes in the families of strongly hereditary and minor closed graph classes. Prior to our study, there was the only one example of a graph problem for which boundary classes were completely described in the family of strongly hereditary classes. Moreover, no boundary classes were known for any graph problem in the family of minor closed classes. In this article, we present several complete descriptions of boundary classes for these two families and some classical graph problems. For the problem of $2$-additive approximation of graph bandwidth, we find a boundary class in the family of minor closed classes. Critical classes are not known for this problem in the other two families of graph classes. Bibliogr. 21.
computational complexity, hereditary class, critical class, efficient algorithm.
PDF file (344 kB)
Journal of Applied and Industrial Mathematics, 2017, 11:1, 99–106
D. S. Malyshev, “Critical elements in combinatorially closed families of graph classes”, Diskretn. Anal. Issled. Oper., 24:1 (2017), 81–96; J. Appl. Industr. Math., 11:1 (2017), 99–106
Citation in format AMSBIB
\paper Critical elements in combinatorially closed families of graph classes
\jour Diskretn. Anal. Issled. Oper.
\jour J. Appl. Industr. Math.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|