Том 27, номер 4, 2020 г., Стр. 5-20

УДК 519.8+518.25
Ворошилов В. В.
Разрез наибольшего веса в орграфе, порожденный минимальным доминирующим множеством

Аннотация:
Пусть $G = (V, A)$ — простой ориентированный граф с заданными неотрицательными весами дуг, $S \subseteq V$ — некоторое подмножество его вершин. Множество $S$ называется доминирующим, если для каждой вершины $j \in$ V\S существуют как минимум одна вершина $i \in S$ и дуга из $i$ в $j$. Доминирующее множество называется минимальным по включению, если оно не содержит в себе доминирующих множеств меньшего размера. Разрезом {$S \to \overline{S}$} называется множество дуг ($i, j$) таких, что $i \in S$, $j \in$ V\S. Весом разреза будем считать суммарный вес входящих в него дуг. В статье исследуется задача поиска разреза {$S \to \overline{S}$} максимального веса среди всех минимальных доминирующих множеств $S$.
Ил. 6, библиогр. 8.

Ключевые слова: ориентированный граф, взвешенный граф, максимальный разрез, минимальное по включению доминирующее множество.

DOI: 10.33048/daio.2020.27.691

Ворошилов Владимир Владимирович ¹
1. Омский гос. университет им. Ф. М. Достоевского,
пр. Мира, 55а, 644077 Омск, Россия
е-mail: voroshil@gmail.com

Статья поступила 27 мая 2020 г.
После доработки — 19 июня 2020 г.
Принята к публикации 22 июня 2020 г.

Литература

[1] Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

[2] Karp R. M. Reducibility among combinatorial problems // Complexity of Computer Computations. Proc. Symp. CCC (Yorktown Heights, USA, Mar. 20–22, 1972). New York: Plenum Press, 1972. P. 85–103.

[3] Ageev A., Hassin R., Sviridenko M. A 0.5-approximation algorithm for max dicut with given sizes of parts // SIAM J. Discrete Math. 2001. Vol. 14, No. 2. P. 246–255.

[4] Lee J., Nagarajan V., Shen X. Max-cut under graph constraints // Integer Programming and Combinatorial Optimization. Proc. 18th Int. Conf. (Liège, Belgium, June 1–3, 2016). Cham: Springer, 2016. P. 50–62. (Lect. Notes Comput. Sci.; Vol. 9682).

[5] Cheston G. A., Fricke G., Hedetniemi S. T., Jacobs D. P. On the computational complexity of upper fractional domination // Discrete Appl. Math. 1990. Vol. 27, No. 3. P. 195–207.

[6] Boria N., Della Croce F., Paschosdef V. Th. On the max min vertex cover problem // Discrete Appl. Math. 2015. Vol. 196. P. 62–71.

[7] Симанчёв Р. Ю., Уразова И. В., Ворошилов В. В., Карпов В. В., Кораблёва А. А. Выбор системы ключевых показателей экономической безопасности региона с использованием модели (0, 1)-программирования // Вестн. Омск. гос. ун-та. Сер. Экономика. 2019. Т. 17, № 3. С. 170–179.

[8] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.