Digital Repository

Parameterized Complexity of Locally Minimal Defensive Alliances

Show simple item record

dc.contributor.author GAIKWAD, AJINKYA en_US
dc.contributor.author MAITY, SOUMEN en_US
dc.contributor.author TRIPATHI, SHUVAM KANT en_US
dc.date.accessioned 2021-04-11T16:46:24Z
dc.date.available 2021-04-11T16:46:24Z
dc.date.issued 2021-01 en_US
dc.identifier.citation Lecture Notes in Computer Science book series (LNCS) Vol. 12601, 135-148. en_US
dc.identifier.isbn 9783-030678982 en_US
dc.identifier.isbn 9783030678999 en_US
dc.identifier.uri http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/5793
dc.description.abstract A defensive alliance in a graph G=(V,E) is a set of vertices S satisfying the condition that every vertex v∈S has at least as many neighbours (including itself) in S as it has in V∖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 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. en_US
dc.language.iso en en_US
dc.publisher Springer Nature en_US
dc.subject Parameterized complexity en_US
dc.subject FPT en_US
dc.subject Treewidth en_US
dc.subject 2021-APR-WEEK2 en_US
dc.subject TOC-APR-2021 en_US
dc.subject 2021 en_US
dc.title Parameterized Complexity of Locally Minimal Defensive Alliances en_US
dc.title.alternative Algorithms and Discrete Applied Mathematics, 135-148. en_US
dc.type Conference Papers en_US
dc.contributor.department Dept. of Mathematics en_US
dc.identifier.doi https://doi.org/10.1007/978-3-030-67899-9_11 en_US
dc.publication.originofpublisher Foreign en_US


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

  • BOOK CHAPTERS [131]
    Book chapters published by IISER Pune Community

Show simple item record

Search Repository


Advanced Search

Browse

My Account