V. E. Alekseev, D. V. Zakharova, “Independence sets of graphs with bounded minors of the augmented incidence matrix”, Diskretn. Anal. Issled. Oper., 2010, Volume 17, Issue 1,Pages <nobr>3

This article is cited in 12 papers

Independence sets of graphs with bounded minors of the augmented incidence matrix

V. E. Alekseev, D. V. Zakharova

Nizhny Novgorod State University, Nizhny Novgorod, Russia

Abstract: 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.

UDC: 519.17

Received: 02.03.2009