Defensive domination in proper interval graphs
Discrete Applied Mathematics, cilt.331, ss.59-69, 2023 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 331
- Basım Tarihi: 2023
- Doi Numarası: 10.1016/j.dam.2023.01.016
- Dergi Adı: Discrete Applied Mathematics
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Applied Science & Technology Source, Compendex, Computer & Applied Sciences, INSPEC, MathSciNet, zbMATH
- Sayfa Sayıları: ss.59-69
- Anahtar Kelimeler: Defensive domination, Proper interval graph
- Boğaziçi Üniversitesi Adresli: Evet
Özet
The k-defensive domination problem, a variant of the classical domination problem on graphs, seeks a minimum cardinality vertex set providing a surjective defense against any attack on vertices of cardinality bounded by a parameter k, where every vertex under attack is defended by a distinct defender (which can be itself). The problem has been shown to be NP-complete for fixed k; if k is part of the input, the problem is unlikely to be in co-NP. We present efficient algorithms solving this problem on proper interval graphs with k part of the input. The algorithms use a greedy approach that takes advantage of the linear ordering of the endpoints of the intervals associated with the vertices. The first algorithm is based on the interval model and has complexity O(n⋅k) for a graph on n vertices and an attack on at most k vertices. The second one is an improvement of the first and employs bubble representations of proper interval graph to realize an improved complexity of O(n+B⋅logk) for a graph represented by B bubbles.