The computational complexity of three graph problems for instances with bounded minors of constraint matrices

被引：3
|
作者：
Gribanov, D. V. [1 ,2 ]
Malyshev, D. S. [2 ]
机构：
[1] Lobachevsky State Univ, 23 Gagarina Av, Nizhnii Novgorod 603950, Russia
[2] Natl Res Univ, Higher Sch Econ, 25-12 Bolshaja Pecherskaja Ulitsa, Nizhnii Novgorod 603155, Russia
来源：
DISCRETE APPLIED MATHEMATICS | 2017年 / 227卷
基金：
俄罗斯科学基金会;
关键词：
Boolean linear programming; Independent set problem; Dominating set problem; Matrix minor; Efficient algorithm; CLIQUE-WIDTH;
D O I：
10.1016/j.dam.2017.04.025
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We consider boolean linear programming formulations of the independent set, the vertex and the edge dominating set problems and prove their polynomial-time solvability for classes of graphs with (augmented) constraint matrices having bounded minors in the absolute value.(C) 2017 Elsevier B.V. All rights reserved.
引用
收藏
页码：13 / 20
页数：8
相关论文
共 16 条
  • [1] The computational complexity of dominating set problems for instances with bounded minors of constraint matrices
    Malyshev, D. S.
    Gribanov, D., V
    DISCRETE OPTIMIZATION, 2018, 29 : 103 - 110
  • [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] On the computational complexity of dynamic graph problems
    Ramalingam, G
    Reps, T
    THEORETICAL COMPUTER SCIENCE, 1996, 158 (1-2) : 233 - 277
  • [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] A computational complexity comparative study of graph tessellation problems
    Abreu, Alexandre
    Cunha, Luis
    Figueiredo, Celina de
    Kowada, Luis
    Marquezino, Franklin
    Portugal, Renato
    Posner, Daniel
    THEORETICAL COMPUTER SCIENCE, 2021, 858 : 81 - 89
  • [9] 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
  • [10] Computational complexity of computing a partial solution for the Graph Automorphism problems
    Nagoya, Takayuki
    Toda, Seinosuke
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (21-23) : 2064 - 2071
12