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, cilt.37, sa.3, ss.1553-1564, 2022 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 37 Sayı: 3
  • Basım Tarihi: 2022
  • Doi Numarası: 10.17341/gazimmfd.902093
  • Dergi Adı: Journal of the Faculty of Engineering and Architecture of Gazi University
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Art Source, Compendex, TR DİZİN (ULAKBİM)
  • Sayfa Sayıları: ss.1553-1564
  • Anahtar Kelimeler: fundamental cut-sets, Independent sets, kmin tree, spanning tree
  • Marmara Üniversitesi Adresli: Hayır

Özet

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.