Constructing edge extremal triangle-free graphs withbounded maximum degree and matching number using integerprogramming
Maksimum derecesi ve eşleme sayısı sınırlı, kenar sayısı en çok olan üçgen-yoksun çizgelerin tamsayılı programlama ile inşası
- Tez No: 795339
- Danışmanlar: PROF. DR. ZEKİ CANER TAŞKIN, 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: 2023
- 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
E¸sleme sayısı m ile, maksimum derecesi d ile sınırlı bir ¸cizgenin kenar sayısının maksimum de˘geri ve bu ¸cizgenin yapısı halihazırda saptanmı¸stır [2]. Buna ba˘glı olarak, belirli alt¸cizgelerin yasaklanmı¸s oldu˘gu durumlarda bu ¸cizgelerin kenar sayısı yeni bir problem olarak ortaya ¸cıkmı¸stır. Ahanjideh, Ekim, ve Yıldız [3] ¨u¸cgen-yoksun ¸cizgeler ¨ust¨une ¸calı¸smı¸s, d ≥ m ve d < m iken d ≤ 6 ya da Z(d) ≤ m < 2d oldu˘gu durumları ¸c¨ozm¨u¸st¨ur. Buradaki Z(d) de˘geri de yakla¸sık olarak 5d/4'e denk gelmektedir. Buna ek olarak a¸cık kalan durumlardaki kenar sayısı en ¸cok ¸cizgeler i¸cin bir yapı ¨onermi¸slerdir. Biz de onların ¨onerdi˘gi yapıyı kullanarak, kenar sayısı en ¸cok ¸cizgeleri in¸sa etmek i¸cin bir tamsayılı programlama yakla¸sımı ortaya koyuyoruz. Problem form¨ulasyonumuz olduk¸ca simetrik oldu˘gu i¸cin simetri kırma y¨ontemlerine y¨oneliyoruz. Bu ama¸cla orbital dallanma ve ama¸c sarsımı y¨ontemlerini kullanıyoruz. Buna ek olarak olurlu b¨olgeyi ¨ust limit bazlı par¸calara ayıran ve yinelemeli olarak bu b¨ol¨umlerde ¸calı¸san kesin yinelemeli bir metod ¨oneriyoruz. Orbital dallanma ve yinelemeli metodun birle¸simini kullanarak, ¸c¨oz¨ulen durumları m > d durumu i¸cin d < 7'den d < 11 ¸cıkartıyoruz. Bunu yaparken [3]'te sunulan hipotezlerin yeni durumlar i¸cin de sa˘glandı˘gını g¨osterip, onları g¨u¸clendiriyoruz.
Özet (Çeviri)
The maximum number of edges in a graph with matching number m and maximum degree d has been determined in [1], and a structure for an extremal graph has been provided in [2]. Then, finding the edge count of an extremal graph with forbidden subgraphs emerged as a new problem. Ahanjideh, Ekim, and Yıldız [3] worked on triangle-free graphs and solved the cases for d ≥ m and for d < m with either d ≤ 6 or Z(d) ≤ m < 2d, where Z(d) is approximately 5d/4. They also provided a structure for an extremal graph for the rest. Using the structure provided, we develop an integer programming formulation for constructing an extremal graph. The formulation is highly symmetric. We use our implementation of orbital branching and objective perturbation to reduce symmetry. We also propose an exact iterative algorithm that partitions the feasible region based on upper bounds and works iteratively on a limited space. Using a combination of the orbital branching and iterative approaches, we expand the solution into d < 11 instead of d < 7 for m > d and show that conjectures proposed in [3] hold, thus strengthening them.
Benzer Tezler
- Edge-extremal graphs under degree and matching number restrictions
Maksimum derecesi ve eşleme sayısı sınırlı, kenar sayısı en çok olan çizgeler
CEMİL DİBEK
Yüksek Lisans
İngilizce
2016
MatematikBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. TINAZ EKİM AŞICI
- A parallel unstructured finite volume method with an efficient edge based data structure for compressible flows
Verimli bir kenar tabanlı veri yapısı üzerine kurgulanmış yapısal olmayan sonlu hacimler yöntemiyle çalışan paralel bir sıkıştırılabilir akış çözücüsü
SEMİH AKKURT
Yüksek Lisans
İngilizce
2018
Uçak Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET ŞAHİN
- Understanding the relation of cancer and inflammation by constructing structural toll-like receptor pathway
Toll-benzeri reseptörlerin yapısal yolaklarını oluşturarak kanser ile enflamasyon arasındaki ilişkiyi anlamak
EMİNE GÜVEN MAIOROV
Doktora
İngilizce
2015
BiyolojiKoç ÜniversitesiKimya ve Biyoloji Mühendisliği Ana Bilim Dalı
PROF. DR. ZEHRA ÖZLEM KESKİN ÖZKAYA
PROF. DR. ATTİLA GÜRSOY
- Analysis layered structure of proteins and their amino acid interactions by constructing residue networks
Proteinlerin katmanlı yapısının analizi ve residü ağları kurularak aminoasitlerinin etkileşimi
HANDAN KULAN
Yüksek Lisans
İngilizce
2014
BiyomühendislikSabancı ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
PROF. DR. CANAN ATILGAN
- Certain time-frequency representations and their applications
Bazı zaman-frekans dağılımları ve uygulamaları
HALİDE ŞİRİN SELVİ
Yüksek Lisans
İngilizce
1995
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiKEMAL LEBLEBİCİOĞLU