THE MINIMAL DOMINATING SETS IN A DIRECTED GRAPH AND THE KEY INDICATORS SET OF SOCIO–ECONOMIC SYSTEM

Ruslan Yu. Simanchev     (Dostoevsky Omsk State University, Prospect Mira 55a, Omsk, 644077, Russia; Omsk Scientific Center of SB RAS, Prospect K. Marksa 15, Omsk, 644024, Russian Federation)
Inna V. Urazova     (Dostoevsky Omsk State University, Prospect Mira 55a, Omsk, 644077, Russian Federation)
Vladimir V. Voroshilov     (Dostoevsky Omsk State University, Prospect Mira 55a, Omsk, 644077, Russian Federation)

Abstract


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.

Keywords


Combinatorial Optimization, Boolean programming, Minimal dominating set, Key indicators

Full Text:

PDF

References


  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). P. 5–12. (in Russian) DOI: 10.25513/1812-3988.2018.4.5-12
  2. Bazgan C. et al. Upper domination: complexity and approximation. In: Lecture Notes in Comput. Sci., vol. 9843: Combinatorial Algorithms. IWOCA 2016, Mäkinen V. et al. (eds.). Cham: Springer, 2016. P. 241–252. DOI: 10.1007/978-3-319-44543-4_19
  3. Cheston G.A., Fricke G., Hedetniemi S.T., Pokrass Jacobs D. On the computational complexity of upper fractional domination. Discrete Appl. Math., 1990. Vol. 27, No. 3. P. 195–207. DOI: 10.1016/0166-218X(90)90065-K
  4. Cockayne E.J., Favaron O., Payan C., Thomason A.G. Contributions to the theory of domination,   independence and irredundance in graphs. Discrete Math., 1981. Vol. 33, No. 3. P. 249–258. DOI: 10.1016/0012-365X(81)90268-5
  5. Courcelle B., Makowsky A., Rotics U. Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Systems, 2000. Vol. 33, No. 2. P. 125–150. DOI: 10.1007/s002249910009
  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. P. 437–457. DOI: 10.1016/B978-0-12-386870-1.50030-7
  7. Jacobson M.S., Peters K. Chordal graphs and upper irredundance, upper domination and independence. Annals Discrete Math., 1991. Vol. 48. P. 59–69. DOI: 10.1016/S0167-5060(08)71038-0
  8. Korableva A.A., Karpov V.V. Indicators of economic security of the region. Herald Siberian Inst. Business Inform. Tech., 2017. No. 3(23). P. 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, 2015. Vol. 11, No. 23(308). P. 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). P. 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, 2019. Vol. 17, No. 3. P. 170–179. (in Russian) DOI: 10.25513/1812-3988.2019.17(3).170-179
  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. P. 43–47. (in Russian)




DOI: http://dx.doi.org/10.15826/umj.2023.1.014

Article Metrics

Metrics Loading ...

Refbacks

  • There are currently no refbacks.