LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES
Küçük Resim Yok
Tarih
2018
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Yildiz Technical Univ
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
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 = vertical bar E vertical bar, n = vertical bar V vertical bar) iterations. We also consider the question whether a given binary matrix is a 0, 1 characteristic vector of fundamental cuts in the graph G.
Açıklama
Anahtar Kelimeler
Network design, submodular function, fundamental cut sets, linear programming
Kaynak
Sigma Journal of Engineering and Natural Sciences-Sigma Muhendislik Ve Fen Bilimleri Dergisi
WoS Q Değeri
N/A
Scopus Q Değeri
Cilt
36
Sayı
3
