Please use this identifier to cite or link to this item:
http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/6658| Title: | Globally minimal defensive alliances |
| Authors: | GAIKWAD, AJINKYA MAITY, SOUMEN Dept. of Mathematics |
| Keywords: | Algorithms FPT Treewidth W[1]-hard 2022-MAR-WEEK2 TOC-MAR-2022 2022 |
| Issue Date: | Aug-2022 |
| Publisher: | Elsevier B.V. |
| Citation: | Information Processing Letters, 177, 106253. |
| Abstract: | A defensive alliance in an undirected graph is a nonempty set of vertices S satisfying the condition that every vertex has at least as many neighbours (including itself) in S as it has in . We consider the notion of global minimality in this paper. We are interested in globally minimal defensive alliance of maximum size. This problem is known to be NP-hard but its parameterized complexity remains open until now. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that the Globally Minimal Defensive Alliance problem is W[1]-hard when parameterized by the treewidth of the graph. We also present a polynomial-time algorithm when the input graph happens to be a tree. |
| URI: | https://doi.org/10.1016/j.ipl.2022.106253 http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/6658 |
| ISSN: | 0020-0190 |
| Appears in Collections: | JOURNAL ARTICLES |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.