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 KARCİ

Pages : 1553-1564

Doi:10.17341/gazimmfd.902093

View : 30 | Download : 11

Publication Date : 2022-02-28

Article Type : Research Paper

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ı