- Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi
- Vol: 37 Issue: 3
- Pençesiz çizgelerde maksimum-yakın bağımsız küme ve üst sınırları için yeni algoritma
Pençesiz çizgelerde maksimum-yakın bağımsız küme ve üst sınırları için yeni algoritma
Authors : Şeyda Karci, Ali Ari, Ali Karci
Pages : 1553-1564
Doi:10.17341/gazimmfd.902093
View : 17 | Download : 2
Publication Date : 2022-02-28
Article Type : Research
Abstract :Günümüzde çizgelerin bazı problemleri için hala yaklaşık çözüm yöntemleri kullanılmaktadır. Bunlar minimum baskın küme, maksimum bağımsız küme, maksimum hizip, mükemmel eşleştirme, Hamilton devresi bunlardan bir kısmıdır. Bu çalışmada maksimum bağımsız küme bulma problemine polinomsal olan bir yöntemin uygulaması üzerinde durulacaktır. Bu amaçla pençesiz çizgelerden olan kral çizgeleri üzerinde örnek çalışmalar gösterilecektir ve pençesiz çizgeler için maksimum bağımsız kümenin eleman sayısı için analitik bir sınır ortaya konulmaya çalışılacaktır.Keywords : bağımsız küme, açılım ağacı, temel kesme kümeleri, kmin ağacı