The maximum acyclic matching problem
Azami döngüsüz eşleştirme problemi
- Tez No: 787359
- Danışmanlar: PROF. DR. TINAZ EKİM AŞICI
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- 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ı: 36
Özet
Bu tezin amacı, doymuş düğümlerin herhangi bir döngü içermeyen indüklenmiş alt çizgelerinin olduğu Azami Eşleştirme anlamına gelen Azami Döngüsel Eşleştirmeyi bulmaktır. Azami Eşleştirme Problemi, mümkün olan en büyük eşleştirme kümesini bulmaya çalışır. Kombinatoryal algoritma ile çözülebilen literatürde sıklıkla rastlanan bir problemdir. Bununla birlikte, azami döngüsüz eşleştirme problemi için, sadece azami eşleştirmeyi değil, aynı zamanda doymuş düğümlerin indüklenmiş alt çizgelerinin herhangi bir döngüye sahip olmamasını istiyoruz. Bu amaçla, döngüsüzlük kısıtına ihtiyaç vardır. Belirli çizge sınıfları için oluşturulmuş bazı kesin ve yaklaşık algoritmalar olmasına rağmen, genel çizgeler için azami döngüsüz eşleştirmeyi bulan bir algoritma yoktur. Bu çalışmada dört algoritma oluşturulmuştur. Farklı yoğunluk seviyelerine ve boyutlara sahip rastgele oluşturulmuş çizgeler, bunların performanslarını analiz etmek için kullanılır. Algoritmalardan ikisi, Kompakt ve Ayrıştırma formülasyonları olan kesin algoritmalardır. Bunların verimliliğine bağlı olarak, Ayrıştırma daha iyi performans sergilemiştir. Diğer iki algoritma ise Modifikasyon ve Konstrüksiyon yaklaşımı olan buluşsal yöntemlerdir. Hem optimale yaklaşma hem de zaman verimliliği açısından Konstrüksiyon yaklaşımının Modifikasyon yaklaşımından daha iyi performans gösterdiği gözlemlenmiştir. Kesin ve buluşsal yöntemlerin en iyileri karşılaştırıldığında Ayrıştırma formülasyonu optimallik yönünden en iyi performansı göstermiştir ancak büyük boyuta sahip çizgeler için uygulanabilir değildir. Konstrüksiyon yaklaşımı daha kısa zamanda optimala yakın makul sonuçlar verir. Ayrıca çizge boyutu ve yoğunluğu büyüdükçe döngüsüzlük kısıtının etkisinin arttığı görülmektedir.
Özet (Çeviri)
The aim of this thesis is to develop exact and heuristic methods to solve the Maximum Acyclic Matching problem, which deals with obtaining maximum matching such that the subgraph induced by saturated vertices is acyclic. The maximum matching problem tries to find the most extensive possible matching set. It is a well-studied problem that can be solved with combinatorial algorithms. However, for the maximum acyclic matching problem, we are searching for not only a maximum size matching but also we require that the subgraph induced by saturated vertices does not contain any cycles. For this purpose, an additional acyclicity constraint is needed. Even though some exact and approximate algorithms are established for particular graph classes, there is no such algorithm applicable for general graphs to find a maximum acyclic matching. In this study, four algorithms are suggested. Randomly generated graphs with different density levels and sizes are used to analyze their performance. Two of the algorithms are exact algorithms, which are extensive and cutting plane formulations. Based on experimental results, the cutting plane approach performs better since it works also with larger graphs. The other two algorithms are heuristics, which are modification and construction approaches. It is observed that the construction approach performs better than the modification approach in terms of both time efficiency and quality. The construction approach yields feasible and close-to-optimal results in a shorter period. When the results of the best exact and heuristics are compared, the cutting plane algorithm performs better based on optimality. However, it is not applicable for large graphs compared to the construction algorithm. Additionally, it is seen that the effect of acyclicity constraint is increasing while graph size and density are getting larger.
Benzer Tezler
- Semantik veri modellerinde bellekte kalıcı girişler için indeks seçimi
Selection of indexes to memory-resident entities for data models
EDA SÜRÜCÜ
- On equimatchable graphs and well-indumatched graphs
Eşiteşlenebilir çizgeler ve iyi-indüklenmiş çizgeler üzerine
YASEMİN BÜYÜKÇOLAK
Doktora
İngilizce
2022
MatematikGebze Teknik ÜniversitesiMatematik Ana Bilim Dalı
PROF. DR. SİBEL ÖZKAN
PROF. DR. DİDEM GÖZÜPEK KOCAMAN
- Yeni nesil dizelemede optimal iş akışı çizelgeleme
Optimal workflow scheduling in next generation sequencing
GÜLÇİN YILDIZ
Yüksek Lisans
Türkçe
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGebze Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. FATİH ERDOĞAN SEVİLGEN
- On the dimension theory of partially ordered sets and graph coloring
Kısmi sıralı kümelerde boyut kuramı ve çizge renklendirme
MEHMET AKİF YETİM
Yüksek Lisans
Türkçe
2014
MatematikSüleyman Demirel ÜniversitesiMatematik Ana Bilim Dalı
PROF. DR. YUSUF CİVAN
- Bir demiryolu yük vagonunun sayısal yöntemlerle seyir emniyeti ve yorulma dayanımının araştırılması
The numerical investigation of running safety and fatigue analysis of a freight wagon
BERAT GÜRCAN ŞENTÜRK
Yüksek Lisans
Türkçe
2014
Makine Mühendisliğiİstanbul Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
ÖĞR. GÖR. EMİN SÜNBÜLOĞLU