- Sigma Mühendislik ve Fen Bilimleri Dergisi
- Vol: 36 Issue: 3
- LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES
LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES
Authors : Firdovsi Sharifov, Hakan Kutucu
Pages : 835-848
View : 16 | Download : 12
Publication Date : 2018-09-01
Article Type : Research
Abstract :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.Keywords : Network design, submodular function, fundamental cut sets, linear programming