New algorithm for near-maximum independent set and its upper bounds in claw-free graphs Pençesiz çizgelerde maksimum-yakin baǧimsiz küme ve üst sinirlari için yeni algoritma

---

Karci Ş., ARI A., KARCI A.

Journal of the Faculty of Engineering and Architecture of Gazi University, vol.37, no.3, pp.1553-1564, 2022 (SCI-Expanded)

• Publication Type: Article / Article
• Volume: 37 Issue: 3
• Publication Date: 2022
• Doi Number: 10.17341/gazimmfd.902093
• Journal Name: Journal of the Faculty of Engineering and Architecture of Gazi University
• Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Art Source, Compendex, TR DİZİN (ULAKBİM)
• Page Numbers: pp.1553-1564
• Keywords: fundamental cut-sets, Independent sets, kmin tree, spanning tree
• Marmara University Affiliated: No

Abstract

Recently, approximation solution methods are used for some problems of graphs. These are the minimum dominating set, maximum independent set, maximum clique, perfect matching, Hamiltonian circuit. In this study, the application of a polynomial method to the problem of finding maximum independent sets will be emphasized. At this aim, case studies on king graphs, which are one of the claw-free graphs, will be shown and analytical limit for the number of elements of the maximum independent set for clae-free graphs.