LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES


Sharifov F., KUTUCU H.

SIGMA JOURNAL OF ENGINEERING AND NATURAL SCIENCES-SIGMA MUHENDISLIK VE FEN BILIMLERI DERGISI, cilt.36, ss.835-848, 2018 (ESCI İndekslerine Giren Dergi)

  • Cilt numarası: 36 Konu: 3
  • Basım Tarihi: 2018
  • Dergi Adı: SIGMA JOURNAL OF ENGINEERING AND NATURAL SCIENCES-SIGMA MUHENDISLIK VE FEN BILIMLERI DERGISI
  • Sayfa Sayısı: ss.835-848

Ö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.