New algorithm for near-maximum independent set and its upper bounds in claw-free graphs

dc.authoridKarci, Ali/0000-0002-8489-8617
dc.authorwosidKarci, Ali/AAG-5337-2019
dc.contributor.authorKarci, Seyda
dc.contributor.authorAri, Ali
dc.contributor.authorKarc, Ali
dc.date.accessioned2024-08-04T20:10:11Z
dc.date.available2024-08-04T20:10:11Z
dc.date.issued2022
dc.departmentİnönü Üniversitesien_US
dc.description.abstractPurpose: 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.en_US
dc.identifier.doi10.17341/gazimmfd.902093
dc.identifier.endpage1564en_US
dc.identifier.issn1300-1884
dc.identifier.issn1304-4915
dc.identifier.issue3en_US
dc.identifier.scopus2-s2.0-85128723730en_US
dc.identifier.scopusqualityQ2en_US
dc.identifier.startpage1553en_US
dc.identifier.trdizinid508622en_US
dc.identifier.urihttps://doi.org/10.17341/gazimmfd.902093
dc.identifier.urihttps://search.trdizin.gov.tr/yayin/detay/508622
dc.identifier.urihttps://hdl.handle.net/11616/92643
dc.identifier.volume37en_US
dc.identifier.wosWOS:000834843300029en_US
dc.identifier.wosqualityQ4en_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.indekslendigikaynakTR-Dizinen_US
dc.language.isoenen_US
dc.publisherGazi Univ, Fac Engineering Architectureen_US
dc.relation.ispartofJournal of The Faculty of Engineering and Architecture of Gazi Universityen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.subjectIndependent seten_US
dc.subjectSpanning Treeen_US
dc.subjectFundamental cut-setsen_US
dc.subjectKmin treeen_US
dc.titleNew algorithm for near-maximum independent set and its upper bounds in claw-free graphsen_US
dc.typeArticleen_US

Dosyalar