Efficient recognition of equimatchable graphs
Information Processing Letters, cilt.114, sa.1-2, ss.66-71, 2014 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 114 Sayı: 1-2
- Basım Tarihi: 2014
- Doi Numarası: 10.1016/j.ipl.2013.08.002
- Dergi Adı: Information Processing Letters
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.66-71
- Anahtar Kelimeler: Edge dominating set, Equimatchable, Graph algorithms, Maximal matching
- Boğaziçi Üniversitesi Adresli: Evet
Özet
In this paper, we give a new characterization of equimatchable graphs that are graphs with all maximal matchings having the same size. This gives an O(n2m)-algorithm for deciding whether a general graph of order n and with m edges is equimatchable. An O(n4.5) recognition algorithm based on the Gallai-Edmonds Decomposition already follows from Lesk et al. (1984) [8]. Our characterization and algorithm use only some basic knowledge on matchings and can be formulated in a simplier way. Moreover it leads to a better time complexity. © 2013 Elsevier B.V.