EN|RU
|
![]() |
Volume 30, No 1, 2023, P. 28-39 UDC 519.17
Keywords: hereditary graph class, computational complexity, dominating set. DOI: 10.33048/daio.2023.30.742 Grigory S. Dakhno 1 Received May 29, 2022 References[1] V. E. Alekseev, D. V. Korobitsyn, and V. V. Lozin, Boundary classes of graphs for the dominating set problem, Discrete Math. 285 (1–3) 1–6 (2004).[2] D. S. Malyshev, A complexity dichotomy and a new boundary class for the dominating set problem, J. Comb. Optim. 32, 226–243 (2016). [3] V. E. Alekseev, On easy and hard hereditary classes of graphs with respect to the independent set problem, Discrete Appl. Math. 132 (1–3), 17–26 (2003). [4] V. E. Alekseev, R. Boliac, D. V. Korobitsyn, andV. V. Lozin, NP-hard graph problems and boundary classes of graphs, Theor. Comput. Sci. 389 (1–2), 219–236 (2007). [5] D. V. Korobitsyn, Complexity of some problems on hereditary classes of graphs, Diskretn. Mat. 2 (3), 90–96 (1990) [Russian] [Discrete Math. Appl. 2 (2), 191–199 (1992)]. [6] D. S. Malyshev, A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs, Discrete Appl. Math. 203, 117–126 (2016). [7] D. S. Malyshev and P. M. Pardalos, Critical hereditary graph classes: A survey, Optim. Lett. 10 (8), 1593–1612 (2016). [8] D. S. Malyshev, Continued sets of boundary classes of graphs for colorability problems, Diskretn. Anal. Issled. Oper. 16 (5), 41–51 (2009) [Russian]. [9] D. S. Malyshev, Critical graph classes for the edge list-ranking problem, Diskretn. Anal. Issled. Oper. 20 (6), 59–76 (2013) [Russian] [J. Appl. Industr. Math. 8 (2), 245–255 (2014)]. [10] O. J. Murphy, Computing independent sets in graphs with large girth, Discrete Appl. Math. 35 (2), 167–170 (1992). [11] H. Müller and A. Brandstädt, The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs, Theor. Comput. Sci. 53 (2–3), 257–265 (1987). |
|
![]() |
|
© Sobolev Institute of Mathematics, 2015 | |
![]() |
|