LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES

Home Page
About
Submit A Journal
Submit A Conference
Submit Paper/Book
- Submit a Preprint
- Submit a Book
Contact

Sigma Mühendislik ve Fen Bilimleri Dergisi
Volume: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 : 27 | Download : 13

Publication Date : 2018-09-01

Article Type : Research Paper

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 = insert ignore into journalissuearticles values(V, E);. We prove that the simplex algorithm finds an optimal solution in at most m-n+1 insert ignore into journalissuearticles values(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

ORIGINAL ARTICLE URL

* There may have been changes in the journal, article,conference, book, preprint etc. informations. Therefore, it would be appropriate to follow the information on the official page of the source. The information here is shared for informational purposes. IAD is not responsible for incorrect or missing information.