Digital Repository

The Minimum Neighbourhood Problem

Show simple item record

dc.contributor.advisor MAITY, SOUMEN en_US
dc.contributor.author JOSHI, CHINMAY en_US
dc.date.accessioned 2019-05-17T10:12:54Z
dc.date.available 2019-05-17T10:12:54Z
dc.date.issued 2019-04 en_US
dc.identifier.uri http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/2970
dc.description.abstract Given a graph G = (V,E) with n vertices and a positive integer s ≤ n, we want to find a set S ⊆ V of size s such that |N[S]| is minimum, where N[S] denotes closed neighbourhood of S. We call this problem as the minimum neighbourhood problem (MNP). In this project, we give a parameterized algorithm which takes as input a graph G, its tree decomposition with width at most k, and a positive integer s, and returns |N[S]| such that S ⊆ V , |S| = s and S has minimum neighbours in G, where the parameter is k. en_US
dc.language.iso en en_US
dc.subject 2019
dc.subject Tree Decomposition en_US
dc.subject Treewidth en_US
dc.subject Fixed Parameter Tractable en_US
dc.subject Dynamic Programming en_US
dc.title The Minimum Neighbourhood Problem en_US
dc.type Thesis en_US
dc.type.degree BS-MS en_US
dc.contributor.department Dept. of Mathematics en_US
dc.contributor.registration 20141076 en_US


Files in this item

This item appears in the following Collection(s)

  • MS THESES [1705]
    Thesis submitted to IISER Pune in partial fulfilment of the requirements for the BS-MS Dual Degree Programme/MSc. Programme/MS-Exit Programme

Show simple item record

Search Repository


Advanced Search

Browse

My Account