The minimal dominating sets in a directed graph and the key indicators set of socio-economic system

Ruslan Yu. Simanchev   ; Inna V. Urazova   ; Vladimir V. Voroshilov

Ural mathematical journal, Tome 9 (2023) no. 1, pp. 153-161

Résumé

The paper deals with a digraph with non-negative vertex weights. A subset $W$ of the set of vertices is called dominating if any vertex that not belongs to it is reachable from the set $W$ within precisely one step. A dominating set is called minimal if it ceases to be dominating when removing any vertex from it. The paper investigates the problem of searching for a minimal dominating set of maximum weight in a vertex-weighted digraph. An integer linear programming model is proposed for this problem. The model is tested on random instances and the real problem of choosing a family of key indicators in a specific socio-economic system. The paper compares this model with the problem of choosing a dominating set with a fixed number of vertices.

Détail

Keywords: combinatorial optimization, boolean programming, minimal dominating set, key indicators.

Bibliographie

[1] Agalakov A. S., Simanchev R. Yu., Urazova I. V., “On the approach to construction of the key indicators system of economic security”, Herald of Omsk University. Ser. Economics, 2018, no. 4(64), 5—12 (in Russian) | DOI

[2] Bazgan C. et al., “Upper domination: complexity and approximation”, Lecture Notes in Comput. Sci., Combinatorial Algorithms, IWOCA 2016, v. 9843, eds. Mäkinen V. et al., Springer, Cham, 2016, 241–252 | DOI | MR | Zbl

[3] Cheston G. A., Fricke G., Hedetniemi S. T., Pokrass Jacobs D., “On the computational complexity of upper fractional domination”, Discrete Appl. Math., 27:3 (1990), 195–207 | DOI | MR | Zbl

[4] Cockayne E. J., Favaron O., Payan C., Thomason A. G., “Contributions to the theory of domination, independence and irredundance in graphs”, Discrete Math., 33:3 (1981), 249–258 | DOI | MR | Zbl

[5] Courcelle B., Makowsky A., Rotics U., “Linear time solvable optimization problems on graphs of bounded clique-width”, Theory Comput. Systems, 33:2 (2000), 125–150 | DOI | MR | Zbl

[6] Hare E. O., Hedetniemi S. T., Laskar R. C., Peters K., Wimer T., “Linear-time computability of combinatorial problems on generalized-series-parallel graphs”, Discrete Algorithms and Complexity, 1987, 437–457 | DOI | MR | Zbl

[7] Jacobson M. S., Peters K., “Chordal graphs and upper irredundance, upper domination and independence”, Annals Discrete Math., 48 (1991), 59–69 | DOI | MR

[8] Korableva A. A., Karpov V. V., “Indicators of economic security of the region”, Herald Siberian Inst. Business Inform. Tech., 2017, no. 3(23), 36–42 (in Russian)

[9] Kuznetsov D. A., Rudenko M. N., “The system of indicators for evaluating the national economic security”, National Interests: Priorities and Security, 11:23(308) (2015), 59–68 (in Russian)

[10] Loginov K. K., “Analysis of indicators of regional economic safety”, The Russian Automobile and Highway Industry J., 2015, no. 2(42), 132–139 (in Russian)

[11] Simanchev R. Yu., Urazova I. V., Voroshilov V. V., Karpov V. V., Korableva A. A., “Selection the key indicators system of the region economic security with use of the (0,1)-programming model”, Herald of Omsk University. Ser. Economics, 17:3 (2019), 170–179 (in Russian) | DOI | MR

[12] Vorona-Slivinskaya L. G., Lobanov M. V., “Problems in selection of state economic security indicators and parametrization of their threshold characters”, Bull. St. Petersburg University of the State Fire Service of the Ministry of Emergency Situations of Russia, 2009, no. 4, 43–47 (in Russian)