Çizgelerde eşli baskın küme probleminin çözümünde merkeziyet temelli bir çözüm yöntemi önerme
Proposing a centrality-based solution method for the paired dominating set problem in graphs
- Tez No: 1023614
- Danışmanlar: PROF. DR. ALİ KARCI, DR. ÖĞR. ÜYESİ MURAT DEMİR
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2026
- Dil: Türkçe
- Üniversite: İnönü Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Yazılım Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Çizge teorisi, mühendislik uygulamalarında önemli bir role sahiptir. Birçok bilimsel ve mühendislik tabanlı problemi, ağ yapısı şeklinde modelleyerek analiz etmek ve çözmek yaygın olarak kullanılmaktadır. Öte yandan, çizge teorisindeki birçok problem NP-zor veya NP-tamamlanmış olarak sınıflandırılır ve bu nedenle polinom zamanında çözülemez. Polinom zamanında çözümler elde etmek için çeşitli yaklaşımlar önerilmiştir. Bu tez çalışmasında optimal deterministik bir algoritma önerilmektedir. Eşli baskın küme oluşumunda merkeziyet metrikleri kullanılmış; her çift için birincil lider düğümü ve onun yedek (bekleme) düğümü olarak görev yapan ikincil düğümü belirleyen bir çözüm sunulmuştur. Önerilen yöntem, çeşitli boyut ve özelliklere sahip ağlara uygulanmış ve neredeyse tüm durumlarda tam kapsama sağlanmıştır. Yani seçilen düğümlerin oluşturduğu kümenin dışında kalan her düğüm bu kümedeki en az bir elemanla komşudur. Dahası, yaklaşım, özellikle büyük ölçekli ağlar için zaman karmaşıklığı açısından verimlilik sağlamaktadır.
Özet (Çeviri)
Graph theory plays an important role in engineering applications. Many scientific and engineering-based problems are commonly modeled as network structures and analyzed using graph-theoretical approaches. However, many problems in graph theory are classified as NP-hard or NP-complete, and therefore cannot generally be solved in polynomial time. Various approaches have been proposed to obtain efficient solutions for such problems. In this thesis, an optimal deterministic algorithm is proposed. Centrality metrics are utilized in the construction of the paired dominating set, and a solution is presented that determines a primary leader node for each pair along with a secondary node acting as its backup (standby) node. The proposed method has been applied to networks with various sizes and structural properties, and nearly full coverage has been achieved in almost all cases. In other words, every node outside the selected set is adjacent to at least one node belonging to the set.Furthermore, the proposed approach demonstrates efficiency in terms of time complexity, particularly for large-scale networks.
Benzer Tezler
- Integer programming approaches to two domination related problems in graph theory
Çizge teorisindeki iki baskın küme varyantına tamsayılı programlama yaklaşımları
ÇINAR ARI
Yüksek Lisans
İngilizce
2025
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUSTAFA KEMAL TURAL
- New structural aspects of domination and independence in graph theory
Çizge kuramında baskınlık ve bağımsızlığın yeni yapısal yönleri
HADI ALIZADEH
Doktora
İngilizce
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGebze Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. DİDEM GÖZÜPEK KOCAMAN
- Türkiye'de antikomünist faaliyetler: propaganda araçları, teşekküller ve portreler(1945-1971)
Anti-communist activities in Turkey: Propaganda vehicles, institutions and portraits (1945-1971)
ABDULAZİM ŞİMŞEK
- Refik Epikman yaşamı-sanatı-sanat eğitimciliği
Başlık çevirisi yok
FATMA TALİA YAĞIZ
Yüksek Lisans
Türkçe
1990
Güzel SanatlarGazi ÜniversitesiEl Sanatları Eğitimi Ana Bilim Dalı
YRD. DOÇ. DR. GÖNÜL GÜLTEKİN
- Architecture of constraints: A mass customization oriented approach for housing design
Kısıtlarla tanımlanan mimarlık: Kitlesel özelleştirme odaklı konut tasarımı
BENGİSU İLKSOY
Yüksek Lisans
İngilizce
2015
Mimarlıkİstanbul Teknik ÜniversitesiMimarlık Ana Bilim Dalı
DOÇ. DR. MİNE ÖZKAR KABAKÇIOĞLU