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

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...

Full description

Saved in:
Bibliographic Details
Published in:Ural mathematical journal 2023-07, Vol.9 (1), p.153
Main Authors: Simanchev, Ruslan Yu, Urazova, Inna V., Voroshilov, Vladimir V.
Format: Article
Language:English
Subjects:
combinatorial optimization, boolean programming, minimal dominating set, key indicators
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2414-3952
2414-3952
DOI:10.15826/umj.2023.1.014