Complexity of the max cut Problem with the Minimal Domination Constraint

被引：0
作者：
Voroshilov V.V. [1 ]
机构：
[1] Dostoevsky Omsk State University, Omsk
来源：
Journal of Applied and Industrial Mathematics | 2022年 / 16卷 / 01期
关键词：
approximation; cutset; dominating set; graph; optimization problem; weighted graph;
D O I：
10.1134/S1990478922010161
中图分类号：
学科分类号：
摘要：
Abstract: Let (Formula presented.)be a simple weighted undirected graph with nonnegative edge weights. LetD be a minimal dominating set in G. The cutset induced by D is the set of edges with one vertex in the set D and the other in (Formula presented.). The weight of the cutset is the total weight of all its edges. The paper dealswith the problem of finding a cutset with the maximum weight among all minimal dominatingsets. In particular, the nonexistence of a polynomial approximation algorithm with a ratio betterthan (Formula presented.) in the case of (Formula presented.) is proved. © 2022, Pleiades Publishing, Ltd.
引用
收藏
页码：168 / 174
页数：6
相关论文
共 50 条
[21]   On the Complexity of BROADCAST DOMINATION and MULTIPACKING in Digraphs [J].
Foucaud, Florent ;
Gras, Benjamin ;
Perez, Anthony ;
Sikora, Florian .
COMBINATORIAL ALGORITHMS, IWOCA 2020, 2020, 12126 :264-276
[22]   On the complexity of some hop domination parameters [J].
Rad, Nader Jafari ;
Shabani, Elahe .
ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2019, 7 (01) :77-89
[23]   On the MAX MIN VERTEX COVER problem [J].
Boria, Nicolas ;
Della Croce, Federico ;
Paschos, Vangelis Th. .
DISCRETE APPLIED MATHEMATICS, 2015, 196 :62-71
[24]   On the MAX MIN VERTEX COVER Problem [J].
Boria, Nicolas ;
Della Croce, Federico ;
Paschos, Vangelis Th. .
APPROXIMATION AND ONLINE ALGORITHMS, WAOA 2013, 2014, 8447 :37-48
[25]   On the parameterized complexity of [1, j]-domination problems [J].
Meybodi, Mohsen Alambardar ;
Fomin, Fedor, V ;
Mouawad, Amer E. ;
Panolan, Fahad .
THEORETICAL COMPUTER SCIENCE, 2020, 804 :207-218
[26]   Complexity of majority monopoly and signed domination problems [J].
Mishra, Sounaka .
JOURNAL OF DISCRETE ALGORITHMS, 2012, 10 (01) :49-60
[27]   Domination and Cut Problems on Chordal Graphs with Bounded Leafage [J].
Galby, Esther ;
Marx, Daniel ;
Schepper, Philipp ;
Sharma, Roohani ;
Tale, Prafullkumar .
ALGORITHMICA, 2024, 86 (05) :1428-1474
[28]   ON THE COMPUTATIONAL COMPLEXITY ASPECTS OF PERFECT ROMAN DOMINATION [J].
Mirhoseini, S. H. ;
Rad, N. jafari .
JOURNAL OF ALGEBRAIC SYSTEMS, 2023, 10 (02)
[29]   Roman {3}-domination in graphs: Complexity and algorithms [J].
Chaudhary, Juhi ;
Pradhan, Dinabandhu .
DISCRETE APPLIED MATHEMATICS, 2024, 354 :301-325
[30]   Domination and Cut Problems on Chordal Graphs with Bounded Leafage [J].
Esther Galby ;
Dániel Marx ;
Philipp Schepper ;
Roohani Sharma ;
Prafullkumar Tale .
Algorithmica, 2024, 86 :1428-1474
12345