ENRU
English version: Journal of Applied and Industrial Mathematics, 2017, 11:1, 99106 

Volume 24, No 1, 2017, P. 8196 UDC 519.17
Keywords: computational complexity, hereditary class, critical class, efficient algorithm. DOI: 10.17377/daio.2017.24.523 Dmitry S. Malyshev ^{1,2} Received 11 January 2016 References[1] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness, Freeman, San Francisco, 1979. Translated under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi, Mir, Moscow, 1982 [Russian].[2] D. S. Malyshev, Continuum sets of boundary graph classes for the colorability problems, Diskretn. Anal. Issled. Oper., 16, No. 5, 41–51, 2009 [Russian]. [3] D. S. Malyshev, On minimal hard classes of graphs, Diskretn. Anal. Issled. Oper., 16, No. 6, 43–51, 2009 [Russian]. [4] D. S. Malyshev, Classes of graphs critical for the edge listranking problem, Diskretn. Anal. Issled. Oper., 20, No. 6, 59–76, 2013 [Russian]. Translated in J. Appl. Ind. Math., 8, No. 2, 245–255, 2014. [5] V. E. Alekseev, On easy and hard hereditary classes of graphs with respect to the independent set problem, Discrete Appl. Math., 132, No. 1–3, 17–26, 2003. [6] V. E. Alekseev, R. Boliac, D. V. Korobitsyn, and V. V. Lozin,NPhard graph problems and boundary classes of graphs, Theor. Comput. Sci., 389, No. 1–2, 219–236, 2007. [7] V. E. Alekseev, D. V. Korobitsyn, and V. V. Lozin, Boundary classes of graphs for the dominating set problem, Discrete Math., 285, No. 1–3, 1–6, 2004. [8] S. Arnborg and A. Proskurowski, Linear time algorithms for NPhard problems restricted to partial ktrees, Discrete Appl. Math., 23, No. 1, 11–24, 1989. [9] H. L. Bodlaender, Dynamic programming on graphs with bounded treewidth, in Automata, Languages and Programming (Proc. 15th Int. Colloq., Tampere, Finland, July 11–15, 1988), pp. 105–118, SpringerVerlag, Heidelberg, 1988 (Lect. Notes Comput. Sci., Vol. 317). [10] H. L. Bodlaender, A partial $k$arboretum of graphs with bounded treewidth, Theor. Comput. Sci., 209, No. 1–2, 1–45, 1998. [11] R. Boliac and V. V. Lozin, On the cliquewidth of graphs in hereditary classes, in Algorithms and Computation (Proc. 13th Int. Symp., Vancouver, Canada, Nov. 21–23, 2002), pp. 44–54, Springer, Heidelberg, 2002 (Lect. Notes Comput. Sci., Vol. 2518). [12] B. Courcelle, J. Makowsky, and U. Rotics, Linear time solvable optimization problems on graphs of bounded cliquewidth, Theory Comput. Syst., 33, No. 2, 125–150, 2000. [13] C. Dubey, U. Feige, and W. Unger, Hardness results for approximating the bandwidth, J. Comput. Syst. Sci., 77, No. 1, 62–90, 2011. [14] M. R. Fellows, D. Lokshtanov, N. Misra, F. A. Rosamond, and S. Saurabh, Graph layout problems parameterized by vertex cover, in Algorithms and Computation (Proc. 19th Int. Symp., Gold Coast, Australia, Dec. 15–17, 2008), pp. 294–305, Springer, Heidelberg, 2008 (Lect. Notes Comput. Sci., Vol. 5369). [15] F. Gurski and E. Wanke, Line graphs of bounded cliquewidth, Discrete Math., 307, No. 22, 2734–2754, 2007. [16] D. Kobler and D. Rotics, Edge dominating set and colorings on graphs with fixed cliquewidth, Discrete Appl. Math., 126, No. 2–3, 197–221, 2003. [17] Z. Miller, The bandwidth of caterpillar graphs, Congr. Numerantium, 33, 235–252, 1981. [18] D. Muradian, The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NPcomplete, Theor. Comput. Sci., 307, No. 3, 567–572, 2003. [19] N. Robertson and P. Seymour, Graph minors V: Excluding a planar graph, J. Comb. Theory, Ser. B, 41, No. 1, 92–114, 1986. [20] N. Robertson and P. Seymour, Graph minors XX: Wagner’s conjecture, J. Comb. Theory, Ser. B, 92, No. 2, 325–357, 2004. [21] J. B. Saxe, Dynamicprogramming algorithms for recognizing smallbandwidth graphs in polynomial time, SIAM J. Algebraic Discrete Methods, 1, No. 4, 363–369, 1980. 

© Sobolev Institute of Mathematics, 2015  