Solving perfect graph modification problems and generating perfect graphs
Kusursuz çizge değiştirme problemlerinin çözülmesi ve kusursuz çizgelerin üretilmesi
- Tez No: 972486
- Danışmanlar: PROF. DR. TINAZ EKİM
- 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: Boğaziçi Ü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
Çizge değiştirme problemleri, çeşitli çizge sınıfları için kapsamlı biçimde incelenmiş olup, literatürde bu problemlerle ilgili çok sayıda hesaplama karmaşıklığı sunan çalışma bulunmaktadır. Bununla birlikte, NP-zor durumların üstesinden gelmek için sunulan kesin algoritmalar nispeten azdır. Bu çalışmada, minimum kusursuz düzenleme, minimum kusursuz tamamlama, minimum kusursuz silme ve kusursuz sandviç problemleri için tamsayılı programlamaya dayalı kesin çözüm yöntemleri tanıtılmaktadır. Düzenleme problemi, bir çizgeyi kusursuz bir çizge haline dönüştürmek için gereken minimum ayrıt ekleme ve silme sayısını ararken, tamamlama problemi değişiklikleri yalnızca ayrıt eklemeleri ve silme problemi yalnızca ayrıt silmeleri ile sınırlandırır. Kusursuz sandviç problemi ise bir karar problemi olarak formüle edilir ve girdi olarak verilen çizgenin var olmayan ayrıtlarının yalnızca belirli bir altkümesinden bazıları ayrıta çevrilerek kusursuz bir çizge üretilip üretilemeyeceğini sorgular. Yaklaşımımız, Güçlü Kusursuz Çizge Teoremini kullanarak, tek delikleri ve bunların tümleyenlerini bir tamsayı programlama modeli içinde doğrusal kısıtlamalar olarak kodlamaktadır. Kısıtlamaların sayısının üstel büyümesi nedeniyle, daha büyük çizgeleri ele almak için yöntemler sunuyoruz. İhlal edilen kısıtları dinamik olarak tespit eden bir kesen düzlem algoritması öneriyoruz. Kesme düzlemi algoritmasının performansını güçlendirmek için, rastgele çizgelerde beklenen tek delik ve tümleyenlerinin sayısını analiz ediyoruz. Buna ek olarak, verilen çizgeyi kusursuz çizgeye dönüştüren buluşsal bir algoritma tanıtıyoruz ve bu algoritmayı kesen düzlem algoritmamızın içinde daha iyi üst sınırlar bulmak için kullanıyoruz. Yöntemlerimizin performansını yaptığımız deneylerle değerlendiriyoruz. Son olarak, önerdiğimiz buluşsal algoritmayı çizge üretme bakış açısından değerlendiriyoruz ve ürettiği kusursuz çizgelerin yapılarını inceliyoruz.
Özet (Çeviri)
Graph modification problems have been extensively explored for various graph classes, with the literature offering numerous NP-completeness proofs and polynomial time algorithms. However, exact algorithms for tackling NP-hard cases remain relatively scarce. In this study, we introduce exact solution methods based on integer programming for the minimum perfect editing, the minimum perfect completion, the minimum perfect deletion, and the perfect sandwich problems. The editing problem seeks the minimum number of edge additions and deletions required to transform a graph into a perfect graph, while the completion problem restricts modifications to only edge additions and the deletion problem restricts to only edge deletions. The perfect sandwich problem, formulated as a decision problem, asks whether a perfect graph can be obtained by adding edges from a specified subset of non-edges. Our approach leverages the Strong Perfect Graph Theorem, encoding odd holes and odd antiholes as linear constraints within an integer programming model. Due to the exponential number of constraints, we develop methods to handle larger graphs. We propose a cutting plane algorithm that dynamically identifies and adds violated constraints based on detected odd holes and odd antiholes. To improve the efficiency of the cutting plane algorithm, we analyze the expected number of odd holes and odd antiholes in random graphs. Additionally, we introduce a heuristic algorithm that transforms a graph into a perfect one, which provides better upper bounds for the editing and completion problems. We validate the effectiveness of our methods through computational experiments. Finally, we consider the proposed heuristic from graph generation perspective, and examine the structure of generated perfect graphs.
Benzer Tezler
- Evaluation of vector and graph-based search methods in a banking knowledge platform using advanced language models
Bankacılık bilgi platformu için vektör ve grafik temelli arama yöntemlerinin gelişmiş dil modelleriyle değerlendirilmesi
BÜNYAMİN BAKIR
Yüksek Lisans
İngilizce
2025
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiBüyük Veri ve İş Analitiği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ SÜHA TUNA
- Graflarda merkezler ve uzaklıklara ilişkin kavramlar
Concepts related to centers and distances in graphs
MEHMET ÜMİT GÜRSOY
- Sualtı akustiği uygulamalarında ışın izleme ve yayılım kaybı hesabının kullanılması
Transmission loss calculation with ray tracing method for underwater acoustics problems
BAKİ BATI
Yüksek Lisans
Türkçe
2009
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYıldız Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. A. GÖKHAN YAVUZ
- A comparative study of tree encodings for evolutionary computing
Evrimsel algoritmalar için ağaç yapılarının karşılaştırmalı çalışması
ESİN SAKA
Yüksek Lisans
İngilizce
2005
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. GÖKTÜRK ÜÇOLUK
DOÇ. DR. İSMAİL HAKKI TOROSLU
- V3Ge bileşiğinin fiziksel özelliklerinin ve süperiletkenlik mekanizmasının teorik olarak incelenmesi
Theoretical investigation of the physical properties and superconductivity mechanism of V3Ge compound
SÜLEYMAN BERKUTAY DURSUN
Yüksek Lisans
Türkçe
2024
Fizik ve Fizik MühendisliğiSakarya ÜniversitesiFizik Ana Bilim Dalı
DOÇ. DR. SADIK BAĞCI