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 条
[41]   Min-Max Spaces and Complexity Reduction in Min-Max Expansions [J].
Stephane Gaubert ;
William M. McEneaney .
Applied Mathematics & Optimization, 2012, 65 :315-348
[42]   Min-Max Spaces and Complexity Reduction in Min-Max Expansions [J].
Gaubert, Stephane ;
McEneaney, William M. .
APPLIED MATHEMATICS AND OPTIMIZATION, 2012, 65 (03) :315-348
[43]   Complexity and Approximability of Parameterized MAX-CSPs [J].
Holger Dell ;
Eun Jung Kim ;
Michael Lampis ;
Valia Mitsou ;
Tobias Mömke .
Algorithmica, 2017, 79 :230-250
[44]   Complexity and Approximability of Parameterized MAX-CSPs [J].
Dell, Holger ;
Kim, Eun Jung ;
Lampis, Michael ;
Mitsou, Valia ;
Moemke, Tobias .
ALGORITHMICA, 2017, 79 (01) :230-250
[45]   Distributed Selfish Algorithms for the Max-Cut Game [J].
Auger, D. ;
Cohen, J. ;
Coucheney, P. ;
Rodier, L. .
INFORMATION SCIENCES AND SYSTEMS 2013, 2013, 264 :45-54
[46]   Parameterized Local Search for Max c-Cut [J].
Garvardt, Jaroslav ;
Gruettemeier, Niels ;
Komusiewicz, Christian ;
Morawietz, Nils .
PROCEEDINGS OF THE THIRTY-SECOND INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, IJCAI 2023, 2023, :5586-5594
[47]   Approximate Max k-cut with subgraph guarantee [J].
Kann, V ;
Lagergren, J ;
Panconesi, A .
INFORMATION PROCESSING LETTERS, 1998, 65 (03) :145-150
[48]   Parameterized Complexity of the Spanning Tree Congestion Problem [J].
Bodlaender, Hans L. ;
Fomin, Fedor V. ;
Golovach, Petr A. ;
Otachi, Yota ;
van Leeuwen, Erik Jan .
ALGORITHMICA, 2012, 64 (01) :85-111
[49]   Double vertex-edge domination in graphs: complexity and algorithms [J].
Naresh Kumar, H. ;
Pradhan, D. ;
Venkatakrishnan, Y. B. .
JOURNAL OF APPLIED MATHEMATICS AND COMPUTING, 2021, 66 (1-2) :245-262
[50]   Labeling algorithm for power domination problem of trees [J].
Lyu, Yijia .
APPLIED MATHEMATICS AND COMPUTATION, 2023, 457
12345