KaydedilenlerDerginizi ekleyin

Dergiler / Sigma Mühendislik ve Fen Bilimleri Dergisi / 2026 / Volume: 36 Issue: 3

LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES

Firdovsi Sharıfov(V.M.Glushkov Institute of Cybernetics)0000-0001-8768-3649
Hakan Kutucu(Karabük University, Department of Computer Engineering)0000-0001-7144-7246
Sayfa
—
Yayın Tarihi
2018-09-01
DOI
—
🏛️Bu makalenin bibliyografik verileri ve tam metin bağlantısı DergiPark üzerinden sağlanmıştır.
DergiPark Kaydı ↗
✨

Yapay Zeka Hızlı Bakış & Çıkarımlar

AI Insight
⚡ TL;DR(1 Cümlede Hızlı Çıkarım)

We also consider the question whether a given binary matrix is a 0, 1 characteristic vector of fundamental cuts in the graph G.

📌 3 Maddede Bu Makale

🎯
Amaç & Hipotez: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).
📊
Temel Bulgular & Veri:We prove that the simplex algorithm finds an optimal solution in at most m-n+1 (m = |E|, n = |V|) iterations.
💡
Sonuç & Katkı:We also consider the question whether a given binary matrix is a 0, 1 characteristic vector of fundamental cuts in the graph G.
🔬Tür:Research Article
📍Kapsam:Genişletilmiş Akademik Örneklem
⚙️Değişkenler:Network design · submodular function · fundamental cut sets

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.

🔖

Bu Makaleye Atıf Yap

Sharıfov, F., Kutucu, H. (2018). LINEAR PROGRAMMING PROBLEMS WITH FUNDAMENTAL CUT MATRICES. Sigma Mühendislik ve Fen Bilimleri Dergisi, Volume: 36 Issue: 3. https://ajindex.com/articles/1345078

📄 Tam Metin PDF Okuyucu

📄

PDF görüntüleyici hazırlanıyor...

Kaynakça (14)

  1. C. Berge: Balanced matrices and property (G), Mathematical Programming Studies 12 (1980), 163-175.
  2. K.H. Borgwardt: The simplex method: A probabilistic Analysis, Algorithms and Combinatorics 1, Springer-Verlag, (1987).
  3. F. Fritzsche and F.B. Holt: More polytope meeting the conjectured Hirsch bound, Discrete Math., 205 (1999), 77-84.
  4. M.X. Goemans and D.P. Williamson: A General Approximation Technique for Constrained Forest Problems, SIAM Journal on Computing, 24:2 (1995), 296-317.
  5. T.C. Hu: Optimum communication spanning trees, SIAM Journal on Computing, 3:3 (1974), 188-195.
  6. M. Kaufmann and D. Wagner: Drawing Graphs: Methods and Models, Springer, (2001).
  7. V. Klee and G.J. Minty: How good is the simplex algorithm?, Inequalities-III, Academic Press, New York (1972), 159-175.
  8. K.V. Marintseva, F.A. Sharifov, G.N. Yun: A problem of airport capacity definition, Aeronautic, 5 (2013), 1-13.
  9. J. Oxley: Matroid theory, Oxford University Press, 2nd Ed., New York, (2011).
  10. Schrijver A.: Combinatorial optimization: Polyhedra and efficiency in Algorithms and Combinatorics, Spinger-Verlag, Berlin, Heidelberg, 24, (2003).
  11. F.A. Sharifov and L. Hulianytskyi: Models and Complexity of Problems of Design and Reconstruction of Telecommunication and Transport Systems, Cybernetics and Systems Analysis, 50:5 (2014), 693-700.
  12. P.D. Seymour: Decomposition of Regular Matroids, Journal of Combinatorial Theory, Series B, 28:3 (1980), 305-359.
  13. M.J. Todd: Polynomial expected behaviour of a pivoting algorithm for linear complementarity and linear programming problems, Technical Report No. 595, School of Operations Research and Industrial Engineering, Cornell University, (Ithaca, NY, November 1983), Mathematical Programming, 35 (1986), 173-192.
  14. K. Truemper: Matroid Decomposition, Academic Press, (1992).