Globally minimal defensive alliances

GAIKWAD, AJINKYA; MAITY, SOUMEN

DR Home
→
PUBLICATIONS & PATENTS
→
JOURNAL ARTICLES
→
View Item

dc.contributor.author	GAIKWAD, AJINKYA	en_US
dc.contributor.author	MAITY, SOUMEN	en_US
dc.date.accessioned	2022-03-30T04:09:52Z
dc.date.available	2022-03-30T04:09:52Z
dc.date.issued	2022-08	en_US
dc.identifier.citation	Information Processing Letters, 177, 106253.	en_US
dc.identifier.issn	0020-0190	en_US
dc.identifier.uri	https://doi.org/10.1016/j.ipl.2022.106253	en_US
dc.identifier.uri	http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/6658
dc.description.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.	en_US
dc.language.iso	en	en_US
dc.publisher	Elsevier B.V.	en_US
dc.subject	Algorithms	en_US
dc.subject	FPT	en_US
dc.subject	Treewidth	en_US
dc.subject	W[1]-hard	en_US
dc.subject	2022-MAR-WEEK2	en_US
dc.subject	TOC-MAR-2022	en_US
dc.subject	2022	en_US
dc.title	Globally minimal defensive alliances	en_US
dc.type	Article	en_US
dc.contributor.department	Dept. of Mathematics	en_US
dc.identifier.sourcetitle	Information Processing Letters	en_US
dc.publication.originofpublisher	Foreign	en_US