Geodesic
The complexity of some graph problems with bounded minors of their constraint matrices
Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 18 (2016) no. 3, pp. 19-31

Voir la notice de l'article provenant de la source Math-Net.Ru

The article considers natural formulations of the independent set problem, vertex and edge dominating set problems as integer linear programming problems. For every fixed $C$, authors prove polynomial-time solvability of both dominating set problems in a class of graphs, for which all minors of the vertex and edge adjacency matrices are at most $C$ in the absolute value. The paper also includes a similar result for the independent set problem and for a class of graphs, which is defined by bounding of absolute values of all matrix minors obtained by augmenting of transposed incidence matrices by all-ones vectors.
Keywords: boolean linear programming, independent set problem, dominating set problem
Mots-clés : matrix minor, polynomial-time algorithm. 
@article{SVMO_2016_18_3_a1,
     author = {D. V. Gribanov and D. S. Malyshev},
     title = {The complexity of some graph problems with bounded minors of their constraint matrices},
     journal = {\v{Z}urnal Srednevol\v{z}skogo matemati\v{c}eskogo ob\^{s}estva},
     pages = {19--31},
     publisher = {mathdoc},
     volume = {18},
     number = {3},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SVMO_2016_18_3_a1/}
}
TY  - JOUR
AU  - D. V. Gribanov
AU  - D. S. Malyshev
TI  - The complexity of some graph problems with bounded minors of their constraint matrices
JO  - Žurnal Srednevolžskogo matematičeskogo obŝestva
PY  - 2016
SP  - 19
EP  - 31
VL  - 18
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SVMO_2016_18_3_a1/
LA  - ru
ID  - SVMO_2016_18_3_a1
ER  - 
%0 Journal Article
%A D. V. Gribanov
%A D. S. Malyshev
%T The complexity of some graph problems with bounded minors of their constraint matrices
%J Žurnal Srednevolžskogo matematičeskogo obŝestva
%D 2016
%P 19-31
%V 18
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SVMO_2016_18_3_a1/
%G ru
%F SVMO_2016_18_3_a1
D. V. Gribanov; D. S. Malyshev. The complexity of some graph problems with bounded minors of their constraint matrices. Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 18 (2016) no. 3, pp. 19-31. http://geodesic.mathdoc.fr/item/SVMO_2016_18_3_a1/