Pençesiz çizgelerde maksimum-yakın bağımsız küme ve üst sınırları için yeni algoritma

Öz

Günümüzde çizgelerin bazı problemleri için hala yaklaşık çözüm yöntemleri kullanılmaktadır. Bunlar minimum baskın küme, maksimum bağımsız küme, maksimum hizip, mükemmel eşleştirme, Hamilton devresi bunlardan bir kısmıdır. Bu çalışmada maksimum bağımsız küme bulma problemine polinomsal olan bir yöntemin uygulaması üzerinde durulacaktır. Bu amaçla pençesiz çizgelerden olan kral çizgeleri üzerinde örnek çalışmalar gösterilecektir ve pençesiz çizgeler için maksimum bağımsız kümenin eleman sayısı için analitik bir sınır ortaya konulmaya çalışılacaktır.

Anahtar Kelimeler

• bağımsız küme
• açılım ağacı
• temel kesme kümeleri
• kmin ağacı

Kaynakça

1. 1. D.Duffus, P.Frankl, V.Rödl,” Maximal independent sets in the covering graph of the cube”, Discrete applied mathematics, Vol.161, pp:1203-1208, 2013.
2. 2. Y. Orlovich, J.Blazewicz, A.Dolgui, G.Finke, V.Gordone,” On the complexity of the independent set problem in triangle graphs”, Discrete Mathematics, Vol.311, pp.1670-1680, 2011.
3. 3. T. Karthick,” Weighted independent sets in a subclass of P6-free graphs”, Discrete mathematics, Vol.339, pp.1412-1418, 2016.
4. 4. T. Karthick, F. Maffray,”Weighted independent sets in classes of P6-free graphs”, Discrete applied mathematics, Vol.209, pp.217-226, 2016.
5. 5. T. Karthick, F. Maffray,” Maximum weight independent sets in classes related to claw-free graphs”, Discrete applied mathematics, Vol.216, pp.233-239, 2017.
6. 6. I. Wloch, A.Wloch,” Generalized sequences and k-independent sets in graphs”, Discrete applied mathematics, Vol.158, pp.1966-1970, 2010.
7. 7. D.Galvin,” The independent set sequence of regular bipartite graphs”, Discrete mathematics, Vol.312, pp.2881-2892, 2012.
8. 8. H. Fleischner, G.Sabidussi, V.I.Sarvanov,” Maximum independent sets in 3- and 4-regular Hamiltonian graphs”, Discrete mathematics, vol.310, pp.2742-2749, 2010.

9. 9. A. Zak,” A generalization of an independent set with application to (Kq; k)-stable graphs”, Discrete applied mathematics, Vol.162, pp.421-427, 2014.
10. 10. S.Oh, S.Lee,” Enumerating independent vertex sets in grid graphs”, Linear algebar and its applications, Vol.510, pp.192-204, 2016.
11. 11. C.Ortiz, Villanueva, “Maximal independent sets in caterpillar graphs”, Discrete applied mathematics, Vol.160, pp.259-266, 2012.
12. 12. M.-S. Lin, S.-H.Su,” Counting independent sets in a tolerance graph”, Discrete applied mathematics, vol.181, pp.174-184, 2015.
13. 13. W.Samotij,”Counting independent sets in graphs”, European journal of combinatorics, Vol.48, pp.5-18, 2015.
14. 14. C. Lopez-Ramirez, J.E.G.Gomez, G.D.I. Luna, “Building a maximal independent set for the vertex-coloring problem on planar graphs”, Electronics notes in theoretical computer science, Vol.354, pp.75-89, 2020.
15. 15. A. Karci,”New algorithms for minimum dominating set in any graphs”, Anatolian science – journal of computer sciences, Vol.5, pp.62-70, 2020a.
16. 16. A. Karci,”Finding innovative and efficient solutions to NP-hard and NP-complete problems in graph theory”, Anatolian science – journal of computer sciences, Vol.5, pp.137-143, 2020b.
17. 17. A. Karci,”Efficient algorithms for determining the maximum independent sets in graphs”, Anatolian science – journal of computer sciences, Vol.5, pp.144-149, 2020c.
18. 18. A. Karci, Ş. Karci,”Determination of effective nodes in graphs”, International conference on science, engineering & technology, Mecca, Saudi Arabia, pp.25-28, 2020.
19. 19. K.İnce, A. Karci, “Modelling and statistical analysis of academic collaborations as a new graph type”, Journal of the Faculty of Engineering and Architecture of Gazi University, vol:34, pp:439-459, 2019.
20. 20. A.Baykasoglu,”İş süreçlerinin modelleme/benzetim yazılımı seçimi için “çizge teorisi” ve “matris yöntemi”, temelli bir yaklaşım”, Journal of Engineering and Architecture of Gazi Unversity, Vol:28, pp:555-566, 2013.
21. 21. A.Karci, “Çizge algoritmaları ve çizge bölmeleme”, Fırat Üniversitesi, Fen Bilimleri Enstitüsü, Yüksek Lisans tezi, 1998.