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 条
[31]   MAX-CUT on Samplings of Dense Graphs [J].
Fakcharoenphol, Jittat ;
Vajanopath, Phanu .
2022 19TH INTERNATIONAL JOINT CONFERENCE ON COMPUTER SCIENCE AND SOFTWARE ENGINEERING (JCSSE 2022), 2022,
[32]   MAX-CUT and containment relations in graphs [J].
Kaminski, Marcin .
THEORETICAL COMPUTER SCIENCE, 2012, 438 :89-95
[33]   On perfect Roman domination number in trees: complexity and bounds [J].
Darkooti, Mahsa ;
Alhevaz, Abdollah ;
Rahimi, Sadegh ;
Rahbani, Hadi .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 38 (03) :712-720
[34]   Exact and heuristic algorithms for the domination problem [J].
Inza, Ernesto Parra ;
Vakhania, Nodari ;
Almira, Jose Maria Sigarreta ;
Mira, Frank Angel Hernandez .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2024, 313 (03) :926-936
[35]   Fixed-parameter algorithms for the weighted Max-Cut problem on embedded 1-planar graphs [J].
Dahn, Christine ;
Kriege, Nils M. ;
Mutzel, Petra ;
Schilling, Julian .
THEORETICAL COMPUTER SCIENCE, 2021, 852 :172-184
[36]   Algorithmic complexity of weakly connected Roman domination in graphs [J].
Chakradhar, Padamutham ;
Reddy, Palagiri Venkata Subba ;
Himanshu, Khandelwal .
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2022, 14 (03)
[37]   On perfect Roman domination number in trees: complexity and bounds [J].
Mahsa Darkooti ;
Abdollah Alhevaz ;
Sadegh Rahimi ;
Hadi Rahbani .
Journal of Combinatorial Optimization, 2019, 38 :712-720
[38]   Constraint Satisfaction Problems: Complexity and Algorithms [J].
Bulatov, Andrei A. .
LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS (LATA 2018), 2018, 10792 :1-25
[39]   On the complexity of minimum q-domination partization problems [J].
Das, Sayani ;
Mishra, Sounaka .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 43 (02) :363-383
[40]   Complexity of Maximum Cut on Interval Graphs [J].
Adhikary, Ranendu ;
Bose, Kaustav ;
Mukherjee, Satwik ;
Roy, Bodhayan .
DISCRETE & COMPUTATIONAL GEOMETRY, 2023, 70 (02) :307-322
12345