Please use this identifier to cite or link to this item: http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/2970
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorMAITY, SOUMENen_US
dc.contributor.authorJOSHI, CHINMAYen_US
dc.date.accessioned2019-05-17T10:12:54Z
dc.date.available2019-05-17T10:12:54Z
dc.date.issued2019-04en_US
dc.identifier.urihttp://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/2970-
dc.description.abstractGiven 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.isoenen_US
dc.subject2019
dc.subjectTree Decompositionen_US
dc.subjectTreewidthen_US
dc.subjectFixed Parameter Tractableen_US
dc.subjectDynamic Programmingen_US
dc.titleThe Minimum Neighbourhood Problemen_US
dc.typeThesisen_US
dc.type.degreeBS-MSen_US
dc.contributor.departmentDept. of Mathematicsen_US
dc.contributor.registration20141076en_US
Appears in Collections:MS THESES

Files in This Item:
File Description SizeFormat 
MS_Thesis_20141076.pdfThesis521.29 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.