Article ID Journal Published Year Pages File Type
4949534 Discrete Applied Mathematics 2017 8 Pages PDF
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
The computational complexity of three graph problems for instances with bounded minors of constraint matrices
Authors
, ,