Integer programming approaches to two domination related problems in graph theory
Çizge teorisindeki iki baskın küme varyantına tamsayılı programlama yaklaşımları
- Tez No: 945931
- Danışmanlar: DOÇ. DR. MUSTAFA KEMAL TURAL
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2025
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Bu tezde, iki baskın küme varyantı olan eşli baskınlık ve defansif baskınlık, tamsayılı programlama teknikleri kullanılarak çalışılmıştır. İlk türde, verilen bir basit çizgede, eşli baskın küme olarak adlandırılan mükemmel eşleme içeren bir altçizgeyi indükleyen bir baskın küme bulunması amaçlanmaktadır. Düğümler ve kenarlar üzerinde ağırlıklar tanımlandığı varsayılarak, minimum ağırlıklı bir eşli baskın küme bulma problemi ele alınmıştır. Bu problem için başlangıçta bir tamsayılı programlama formülasyonu önerilmiş, ardından bu formülasyon güçlendirilmiş ve elde edilen doğrusal programlama gevşetmesinin, kısıtlar matrisi her zaman tamamen unimodüler olmasa da, ağaçlar üzerindeki eşli baskın kümelerin insidans vektörlerinin konveks zarfını tanımladığı gösterilmiştir. Ayrıca, eşli baskın küme politopunun incelenmesine başlanmış ve çeşitli geçerli eşitsizlik kümeleri önerilmiştir. Güçlendirilmiş modelin performansı ve geçerli eşitsizliklerin etkisi, sayısal bir çalışma ile rastgele üretilmiş çizgeler üzerinde analiz edilmiştir. İkinci varyant, verilen basit bir çizge ve pozitif bir tamsayı k için; k-defansif baskın küme olarak adlandırılan, çizgenin herhangi k düğümüne yönelik tüm saldırılara karşı savunma yapabilecek bir baskın küme bulmayı amaçlamaktadır. Defansif baskın kümedeki bir düğüm, kapalı komşuluğundaki en fazla bir saldırgana karşı savunma yapabilir. Düğümler üzerinde ağırlıkların tanımlı olduğu varsayımıyla, en düşük ağırlığa sahip bir k-defansif baskın kümenin bulunması problemi incelenmiştir. Bu problem için, üstel sayıda kısıta sahip bir tamsayılı programlama formülasyonu önerilmiş, formülasyon bazı geçerli eşitsizliklerle güçlendirilmiş ve güçlendirilmiş formülasyon, satır üretimi yöntemi kullanılarak uygulanmıştır.
Özet (Çeviri)
In this thesis, two domination variants; namely, paired-domination and defensive domination, are studied using integer programming techniques. The first variant involves finding a dominating set (called a paired-dominating set) in a given simple graph which induces a subgraph that has a perfect matching. Assuming weights on the nodes and the edges, we study the problem of finding a paired-dominating set of minimum weight. For this problem, after proposing an initial integer programming formulation, we strengthen it and show that the linear programming relaxation of the latter characterizes the convex hull of the incidence vectors of paired-dominating sets in trees even though the constraint matrix is not always totally unimodular. Moreover, we initiate the study of the paired-dominating set polytope by proposing several sets of valid inequalities. The performance of the strengthened formulation and the impact of valid inequalities are analyzed via a computational study. The second variant looks for a dominating set (called a k-defensive dominating set) in a given simple graph which can defend against all attacks to any k nodes of the graph for a given positive integer k. A node in our dominating set can defend against at most one attacker in its closed neighborhood. Assuming weights on the nodes, we study the problem of finding a k-defensive dominating set of minimum weight. For this problem, we propose an integer programming formulation with exponentially many constraints, strengthen it via some valid inequalities and implement the strengthened formulation using a row generation procedure.
Benzer Tezler
- Demiryolu yük taşımacılığında optimum katar yükü probleminin incelenmesi
Determination of the optimum train load in railway freight transportation
SADETTİN ÖZEN
- Proses endüstrisinde proses kontrolu problemine hedef programlama ile yaklaşım ve alternatif bir HP algoritması önerisinin bir uygulama üzerinde değerlendirilmesi
An Approach with the technique of goal programming to the problem of process control in process industry and a proposed alternative algorithm for goal programming
ORHAN KURUÜZÜM
Doktora
Türkçe
1986
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ. DR. AYHAN TORAMAN