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 条
  • [1] THE COMPLEXITY OF SECURE DOMINATION PROBLEM IN GRAPHS
    Wang, Haichao
    Zhao, Yancai
    Deng, Yunping
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2018, 38 (02) : 385 - 396
  • [2] Capacitated Domination: Problem Complexity and Approximation Algorithms
    Mong-Jen Kao
    Han-Lin Chen
    D. T. Lee
    Algorithmica, 2015, 72 : 1 - 43
  • [3] Capacitated Domination: Problem Complexity and Approximation Algorithms
    Kao, Mong-Jen
    Chen, Han-Lin
    Lee, D. T.
    ALGORITHMICA, 2015, 72 (01) : 1 - 43
  • [4] Complexity of the weighted max-cut in Euclidean space
    Ageev A.A.
    Kel’manov A.V.
    Pyatkin A.V.
    Ageev, A.A., 1600, Izdatel'stvo Nauka (08): : 453 - 457
  • [5] The Complexity of the Counting Constraint Satisfaction Problem
    Bulatov, Andrei A.
    JOURNAL OF THE ACM, 2013, 60 (05)
  • [6] On relaxations of the max k-cut problem formulations
    Fakhimi, Ramin
    Validi, Hamidreza
    Hicks, Illya V.
    Terlaky, Tamas
    Zuluaga, Luis F.
    OPERATIONS RESEARCH LETTERS, 2023, 51 (05) : 521 - 527
  • [7] Advanced Scatter Search for the Max-Cut Problem
    Marti, Rafael
    Duarte, Abraham
    Laguna, Manuel
    INFORMS JOURNAL ON COMPUTING, 2009, 21 (01) : 26 - 38
  • [8] Complexity of total outer-connected domination problem in graphs
    Panda, B. S.
    Pandey, Arti
    DISCRETE APPLIED MATHEMATICS, 2016, 199 : 110 - 122
  • [9] A discrete dynamic convexized method for the max-cut problem
    Lin, Geng
    Zhu, Wenxing
    ANNALS OF OPERATIONS RESEARCH, 2012, 196 (01) : 371 - 390
  • [10] On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
    Lin, Min Chih
    Mizrahi, Michel J.
    DISCRETE APPLIED MATHEMATICS, 2015, 197 : 53 - 58
12345