Parameterized complexity of locally minimal defensive alliances
Conference on Algorithms and Discrete Applied Mathematics, 2021•Springer
A defensive alliance in a graph G=(V, E) G=(V, E) is a set of vertices S satisfying the
condition that every vertex v ∈ S v∈ S has at least as many neighbours (including itself) in
S as it has in V ∖ SV\S. We consider the notion of local minimality in this paper. We are
interested in locally 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. The three …
condition that every vertex v ∈ S v∈ S has at least as many neighbours (including itself) in
S as it has in V ∖ SV\S. We consider the notion of local minimality in this paper. We are
interested in locally 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. The three …
Abstract
A defensive alliance in a graph is a 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 local minimality in this paper. We are interested in locally 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. The three main results of the paper are the following: (1) when the input graph happens to be a tree, Locally Minimal Strong Defensive Alliance can be solved in polynomial time, (2) Locally Minimal Defensive Alliance is fixed parameter tractable (FPT) when parametrized by neighbourhood diversity, and (3) Locally Minimal Defensive Alliance can be solved in polynomial time for graphs of bounded treewidth.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果