EN|RU
|
![]() |
Volume 29, No 1, 2022, P. 5-17 UDC 519.8+518.25
Keywords: graph, cutset, dominating set, weighted graph, optimization problem, approximation. DOI: 10.33048/daio.2022.29.706 Vladimir V. Voroshilov 1 Received February 19, 2021 References[1] R. Yu. Simanchev, I. V. Urazova, V. V. Voroshilov, V. V. Karpov, and A. A. Korableva, Selection the key indicators system of the region economic security with use of the (0, 1)-programming model, Vestn. Omsk. Univ., Ser. Ekonomika 17 (3), 170–179 (2019) [Russian].[2] G. A. Cheston, G. Fricke, S. T. Hedetniemi, and D. P. Jacobs, On the computational complexity of upper fractional domination, Discrete Appl. Math. 27 (3), 195–207 (1990). [3] N. Boria, F. Della Croce, and V. Th. Paschos, On the max min vertex cover problem, Discrete Appl. Math. 196, 62–71 (2015). [4] V. V. Voroshilov, A maximum dicut in a digraph induced by a minimal dominating set, Diskretn. Anal. Issled. Oper. 27 (4), 5–20 (2020) [Russian] [J. Appl. Ind. Math. 14 (4), 792–801 (2020)]. [5] N. Christofides, Graph Theory: An Algorithmic Approach (Academic Press, London, 1975; Mir, Moscow, 1978 [Russian]). [6] R. M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations (Proc. Symp. CCC, Yorktown Heights, USA, March 20–22, 1972) (Plenum Press, New York, 1972), pp. 85–103. [7] J. Lee, N. Viswanath, and X. Shen, Max-cut under graph constraints, Programming and Combinatorial Optimization (Proc. 18th Int. Conf., Liège, Belgium, June 1–3, 2016) (Springer, Cham, 2016), pp. 50–62 (Lect. Notes Comput. Sci., Vol. 9682). [8] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982 [Russian]). |
|
![]() |
|
© Sobolev Institute of Mathematics, 2015 | |
![]() |
|