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ı: 83
Ö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
- Terrain visibility and guarding problems
Arazi görünürlük ve koruma problemleri
HALUK ELİŞ
Doktora
İngilizce
2017
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. OSMAN OĞUZ
- Genetik algoritma ile kan ve kan ürünleri tedarik zinciri ağ tasarımı: Kızılay Doğu Karadeniz bölge kan merkezi örneği
Blood and blood products supply chain network design using genetic algorithm: Turkish red crescent Eastern Black Sea region blood center case
GÖKHAN AĞAÇ
Doktora
Türkçe
2019
Sağlık Kurumları YönetimiKaradeniz Teknik Üniversitesiİşletme Ana Bilim Dalı
PROF. DR. BİRDOĞAN BAKİ
- Ranking units by target-direction-set value efficiency analysis and mixed integer programming
Hedef-yön-tespitli faydasal etkinlik analizi ve karma tam sayılı programlama ile ünitelerin sıralanması
TAYYAR BÜYÜKBAŞARAN
Yüksek Lisans
İngilizce
2005
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiPROF.DR. MURAT KÖKSALAN
- A bicriteria rescheduling problem on unrelated parallel machines: Network flow and enumeration based approaches
İlgisiz paralel makinelerde iki kriterli yeniden çizelgeleme problemi: Ağ akış ve birerleme tabanlı yaklaşımlar
MELİH ÖZLEN
Doktora
İngilizce
2006
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. MERAL AZİZOĞLU
- Karma modelli düz ve U-tipi montaj hatlarının bazı özel durumlar altında dengelenmesine yönelik çözüm yaklaşımlarının geliştirilmesi
Developing solution approaches for balancing straight and U-type mixed model assembly lines under some particular conditions
NEŞE YALÇIN
Doktora
Türkçe
2011
Endüstri ve Endüstri MühendisliğiErciyes Üniversitesiİşletme Ana Bilim Dalı
PROF. DR. CEMAL ÖZGÜVEN