Linear programming problems with fundamental cut matrices

Sharifov, F., & Kutucu, H.

Sigma J Eng & Nat Sci, 36 (3), 2018, 835-848.


In the paper, we consider a linear programming problem with con-straint matrices whose rows are 0, 1 characteristics vectors of fundamental cuts in a given undirected graph G = (V, E). We prove that the simplex algorithm finds an optimal solution in at most m-n+1 (m = |E|, n = |V|) iterations. We also consider the question whether a given binary matrix is a 0, 1 characteristic vector of fundamental cuts in the graph G.

Ключові слова: Network design, submodular function, fundamental cut sets, linear programming.

Завантажити файл публікації