The computational complexity of dominating set problems for instances with bounded minors of constraint matrices

被引：3
|
作者：
Malyshev, D. S. [1 ]
Gribanov, D., V [1 ,2 ]
机构：
[1] Natl Res Univ, Higher Sch Econ, 25-12 Bolshaja Pecherskaja Ulitsa, Nizhnii Novgorod 603155, Russia
[2] Lobachevsky State Univ, 23 Gagarina Av, Nizhnii Novgorod 603950, Russia
来源：
DISCRETE OPTIMIZATION | 2018年 / 29卷
基金：
俄罗斯科学基金会;
关键词：
Boolean linear programming; Dominating set problem; Matrix minor; Efficient algorithm; CLIQUE-WIDTH; GRAPHS;
D O I：
10.1016/j.disopt.2018.03.002
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We consider boolean linear programming formulations of the vertex and edge dominating set problems and prove their polynomial-time solvability for classes of graphs with constraint matrices having bounded minors in the absolute value. (C) 2018 Elsevier B.V. All rights reserved.
引用
收藏
页码：103 / 110
页数：8
相关论文
共 14 条
  • [1] The computational complexity of three graph problems for instances with bounded minors of constraint matrices
    Gribanov, D. V.
    Malyshev, D. S.
    DISCRETE APPLIED MATHEMATICS, 2017, 227 : 13 - 20
  • [2] The width and integer optimization on simplices with bounded minors of the constraint matrices
    D. V. Gribanov
    A. Y. Chirkov
    Optimization Letters, 2016, 10 : 1179 - 1189
  • [3] The width and integer optimization on simplices with bounded minors of the constraint matrices
    Gribanov, D. V.
    Chirkov, A. Y.
    OPTIMIZATION LETTERS, 2016, 10 (06) : 1179 - 1189
  • [4] Approximation hardness of dominating set problems in bounded degree graphs
    Chlebik, M.
    Chlebikova, J.
    INFORMATION AND COMPUTATION, 2008, 206 (11) : 1264 - 1275
  • [5] On the Computational Complexity of Monotone Constraint Satisfaction Problems
    Hermann, Miki
    Richoux, Florian
    WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2009, 5431 : 286 - 297
  • [6] Technical Perspective Constraint Satisfaction Problems and Computational Complexity
    Jerrum, Mark
    COMMUNICATIONS OF THE ACM, 2010, 53 (09) : 98 - 98
  • [7] The computational complexity of Steiner tree problems in graded matrices
    Dudas, T
    Klinz, B
    Woeginger, GJ
    APPLIED MATHEMATICS LETTERS, 1997, 10 (04) : 35 - 39
  • [8] On the complexity of dominating set problems related to the minimum all-ones problem
    Broersma, Hajo
    Li, Xueliang
    THEORETICAL COMPUTER SCIENCE, 2007, 385 (1-3) : 60 - 70
  • [9] Computational Complexity of Feedback Set and Subset Feedback Set Problems: A Survey
    Bai, Tian
    Xiao, Mingyu
    Jisuanji Yanjiu yu Fazhan/Computer Research and Development, 2025, 62 (01): : 104 - 118
  • [10] Computational complexity of multi-way, dataflow constraint problems
    Trombettoni, G
    Neveu, B
    IJCAI-97 - PROCEEDINGS OF THE FIFTEENTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOLS 1 AND 2, 1997, : 358 - 363
12