Geri Dön

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ı

PDF İndir

  1. Tez No: 795339
  2. Yazar: ALİ ERDEM BANAK
  3. Danışmanlar: PROF. DR. ZEKİ CANER TAŞKIN, PROF. DR. TINAZ EKİM AŞICI
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2023
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 51

Ö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

  1. Tez No

    433957

    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

    İngilizce

    2016

    Endüstri ve Endüstri MühendisliğiBoğaziçi Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. TINAZ EKİM AŞICI

  2. Tez No

    518018

    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

    İngilizce

    2018

    Uçak Mühendisliğiİstanbul Teknik Üniversitesi

    Uçak ve Uzay Mühendisliği Ana Bilim Dalı

    PROF. DR. MEHMET ŞAHİN

  3. Tez No

    302581

    Yumuşak kili zeminlerde taş kolonlarla zemin iyileştirilmesinin laboratuar model deneyleriyle araştırılması

    Investigating behavior of soft soil improved by constructing stone columns with model experiments

    HÜSEYİN EMRAH NAMAL

    Yüksek Lisans

    Türkçe

    Türkçe

    2011

    İnşaat MühendisliğiYıldız Teknik Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. SAADET ARZU BERİLGEN

  4. Tez No

    295912

    Darbeli taş kolonlar (geopier) ile iyileştirilmiş zeminlerin model deneylerle incelenmesi

    Investigation behavior of soil improved by constructing rammed aggregate pile with model experiments

    ŞAMİL ATAMAN

    Yüksek Lisans

    Türkçe

    Türkçe

    2011

    İnşaat MühendisliğiYıldız Teknik Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MEHMET BERİLGEN

  5. Tez No

    414052

    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

    İngilizce

    2015

    BiyolojiKoç Üniversitesi

    Kimya ve Biyoloji Mühendisliği Ana Bilim Dalı

    PROF. DR. ZEHRA ÖZLEM KESKİN ÖZKAYA

    PROF. DR. ATTİLA GÜRSOY

Geri Dön