DSpace Arşivi :: by Yazar "Karci, Seyda" değerine göre listeleniyor

Listeleniyor 1 - 1 / 1

New algorithm for near-maximum independent set and its upper bounds in claw-free graphs
(Gazi Univ, Fac Engineering Architecture, 2022) Karci, Seyda; Ari, Ali; Karc, Ali
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.