Geri Dön

Unit disk graph coloring and its reoptimization

Birim disk çizge boyama ve yeniden eniyilenmesi

PDF İndir

  1. Tez No: 245878
  2. Yazar: ARMAN BOYACI
  3. Danışmanlar: YRD. DOÇ. 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: 2009
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Bölümü
  12. Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  13. Sayfa Sayısı: 97

Özet

Bir takım birim diskin Öklid düzleminde kesişimleri birim disk çizgedir(BDÇ).Özellikle telekomünikasyondaki frekans atama probleminin ¸cözümü için önemli ve NPzorproblemler olan birim disk çizge boyama(BDÇBoya) problemini ve yeniden eniyilenmesiniele aldık. Çalışmanın ilk kısmında, deneysel testler gerçekleşstirerek BDÇBoyaprobleminin alt ve üst sınırlarının kalitesi incelendi. Bazı gözlemlere dayanarak, mevcutO(n4.5) klik algoritmasının ortalama koşu zamanında iyileştirme sağlandı. Ekolarak, iki yeni boyama sezgiseli ve Kempe'nin Zincirlerinden ilham alınarak yenibir iyileştirme yöntemi önerildi. İkinci kısımda ise, köşe ekle/çıkar yeniden eniyilemeproblemleri tanımlandı. Eski örneğe ait eniyi çözüm bilgisine rağmen bu problemlerinNP-zor kaldıklarını gösterdik ve bu nedenle sezgisel yöntemler önerdik. Bu sezgisellerinortalama performansları, deneysel çalışmalar ile tayin edildi. Ayrıca Brelaz'ınardışık boyama algoritmasını köşe ekle yeniden eniyileme problemini ¸çözebilecek şekildeuyarladık.

Özet (Çeviri)

A unit disk graph (UDG) is a graph of intersection of a set of unit disks in Euclidean plane. Motivated by frequency assignment problem in telecommunication, we consider minimum vertex coloring of unit disk graphs (ColorUDG) and its reoptimization which are both NP-hard problems.In the first part of the study, the quality of lower and upper bounds on the optimal value of ColorUDG are investigated by conducting empirical tests. Maximum clique is a lower bound for the minimum coloring. Based on some observations, running time improvement is achieved on the existing $O(n^{4.5})$ maximum clique algorithm. On the other hand, we derive upper bounds by some simple heuristics (sequential algorithms). Two new construction heuristics and a new improvement method are proposed.In the second part, vertex adding/removing reoptimization problems for ColorUDG are defined. Despite the knowledge of the optimum solution of the old instance, we showed that both problems remains NP-hard, therefore some heuristic methods are proposed. The developed reoptimization algorithms, which perform successfully for many instances when applied to randomly generated graphs. Moreover, we modified Brelaz's sequential coloring algorithm to solve exactly vertex adding reoptimization problem.

Benzer Tezler

  1. Tez No

    782215

    Characterizing and detecting cohesive subgroups with applications tosocial and brain network

    Yogun ve uyumlu alt grupları karakterize etme ve tespit etme, sosyal media ağları ve beyin ağlari

    MAKBULE ZEYNEP ERTEM OKTAY

    Doktora

    İngilizce

    İngilizce

    2015

    Endüstri ve Endüstri MühendisliğiTexas A&M University

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

    PROF. DR. SERGİY BUTENKO

  2. Tez No

    275343

    Yapı modellerinin dinamik davranışlarının deneysel ve teorik incelenmesi

    Theoretical end experimental comparison of dynamic structural models

    CEM MERTAYAK

    Yüksek Lisans

    Türkçe

    Türkçe

    2009

    İnşaat MühendisliğiMustafa Kemal Üniversitesi

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

    YRD. DOÇ. HAKAN TÜRKER

  3. Tez No

    66675

    Bilgisayar yardımı ile step motorun hareket kontrolu

    Computer aided control of stepping motors

    LATİF TAŞTAN

    Yüksek Lisans

    Türkçe

    Türkçe

    1997

    Makine Mühendisliğiİstanbul Teknik Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    DOÇ. DR. N. AYDIN HIZAL

  4. Tez No

    55944

    Sahada programlanabilir kapı dizileri ile lojik devre tasarımı

    Başlık çevirisi yok

    VOLKAN SEZER

    Yüksek Lisans

    Türkçe

    Türkçe

    1996

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    PROF.DR. AHMET DERVİŞOĞLU

  5. Tez No

    39485

    Biyotelemetri sistemi

    Biotelemetry systems

    SÜLEYMAN ÖZKAPTAN

    Yüksek Lisans

    Türkçe

    Türkçe

    1994

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    DOÇ.DR. MEHMET KORÜREK

Geri Dön