New algorithm for near-maximum independent set and its upper bounds in claw-free graphs
Küçük Resim Yok
Tarih
2022
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Gazi Univ, Fac Engineering Architecture
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
Purpose: The aim of this paper is to develop algorithms for obtaining independent set in given graph and determine upper bounds for |I| in claw-free graphs. Theory and Methods: The main aim of this paper is to develop algorithms for obtaining near-optimal independent set for any type of graph. A special spanning tree (Kmin) is used for this aim. Kmin is used to obtain the fundamental cut-sets of graphs, and cut-set matrix. The multiplication of incidence matrix and transpose of cut-set matrix gives the first independent set element which has minimum independence number. The Kmin tree is also used to determine the upper bounds for size of independent set in term of minimum degree. Results: The developed algorithms are used for obtaining near-maximum independent set for any given graphs, and this case is the advantage of this algorithm. The Kmin spanning tree is used to obtain the upper bounds for size of independent set, and the obtained inequality is in term of minimum degree in graph. Conclusion: The developed method obtains the near-maximum independent set for any graph type. The upper bound for size of independent set is obtained based Kmin and minimum degree in graph.
Açıklama
Anahtar Kelimeler
Independent set, Spanning Tree, Fundamental cut-sets, Kmin tree
Kaynak
Journal of The Faculty of Engineering and Architecture of Gazi University
WoS Q Değeri
Q4
Scopus Q Değeri
Q2
Cilt
37
Sayı
3
