Geodesic
Independence sets of graphs with bounded minors of the augmented incidence matrix
Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 1, pp. 3-10.

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

We characterize the graphs with bounded minors of augmented incidence matrix. We also prove that the independence set problem can be solved in polynomial time for graphs with bounded minors of incidence matrix with an added column of units. Bibl. 6.
Keywords: augmented incidence matrix, minor, independence set problem. 
@article{DA_2010_17_1_a0,
     author = {V. E. Alekseev and D. V. Zakharova},
     title = {Independence sets of graphs with bounded minors of the augmented incidence matrix},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {3--10},
     publisher = {mathdoc},
     volume = {17},
     number = {1},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2010_17_1_a0/}
}
TY  - JOUR
AU  - V. E. Alekseev
AU  - D. V. Zakharova
TI  - Independence sets of graphs with bounded minors of the augmented incidence matrix
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2010
SP  - 3
EP  - 10
VL  - 17
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2010_17_1_a0/
LA  - ru
ID  - DA_2010_17_1_a0
ER  - 
%0 Journal Article
%A V. E. Alekseev
%A D. V. Zakharova
%T Independence sets of graphs with bounded minors of the augmented incidence matrix
%J Diskretnyj analiz i issledovanie operacij
%D 2010
%P 3-10
%V 17
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2010_17_1_a0/
%G ru
%F DA_2010_17_1_a0
V. E. Alekseev; D. V. Zakharova. Independence sets of graphs with bounded minors of the augmented incidence matrix. Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 1, pp. 3-10. http://geodesic.mathdoc.fr/item/DA_2010_17_1_a0/

[1] Alekseev V. E., “Verkhnyaya otsenka chisla maksimalnykh nezavisimykh mnozhestv grafa”, Diskret. matematika, 19:3 (2007), 84–88 | MR | Zbl

[2] Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I., Lektsii po teorii grafov, Nauka, M., 1990, 384 pp. | MR | Zbl

[3] Zykov A. A., Osnovy teorii grafov, Nauka, M., 1987, 382 pp. | MR | Zbl

[4] Shevchenko V. N., Kachestvennye voprosy tselochislennogo programmirovaniya, Nauka, M., 1995, 192 pp. | MR | Zbl

[5] Grossman J. W., Kilkarni D. M., Schochetman I. E., “On the minors of an incidence matrix and its Smith normal form”, Linear Algebra Appl., 218 (1995), 213–224 | DOI | MR | Zbl

[6] Tsukigama S., Ide M., Ariochi H., Ozaki H., “A new algorithm for generating all the maximal independent sets”, SIAM J. Comput., 6:3 (1977), 505–517 | DOI | MR