1. DSpace@IISERMohali
  2. Publications of IISER Mohali
  3. Research Articles
Please use this identifier to cite or link to this item: http://hdl.handle.net/123456789/3453
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGupta, Naman-
dc.date.accessioned2020-12-30T10:03:19Z-
dc.date.available2020-12-30T10:03:19Z-
dc.date.issued2020-
dc.identifier.citationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 12016 LNCS, pp. 439-450en_US
dc.identifier.other10.1007/978-3-030-39219-2_35-
dc.identifier.urihttps://link.springer.com/chapter/10.1007%2F978-3-030-39219-2_35-
dc.identifier.urihttp://hdl.handle.net/123456789/3453-
dc.descriptionOnly IISERM authors are available in the record.-
dc.description.abstractConflict free q-Colouring of a graph G refers to the colouring of a subset of vertices of G using q colours such that every vertex has a neighbour of unique colour. In this paper, we study the Minimum Conflict free q-Colouring problem. Given a graph G and a fixed constant q, Minimum Conflict free q-Colouring is to find a Conflict free q-Colouring of G that minimises the number of coloured vertices. We study the Minimum Conflict free q-Colouring problem parameterized by the treewidth of G. We give an FPT algorithm for this problem and also prove running time lower bounds under Exponential Time Hypothesis (ETH) and Strong Exponential Time Hypothesis (SETH).en_US
dc.language.isoenen_US
dc.publisherSpringer Linken_US
dc.subjectConflict free colouring of graphsen_US
dc.subjectParameterized complexityen_US
dc.subjectFPT algorithmsen_US
dc.subjectTreewidthen_US
dc.titleMinimum Conflict Free Colouring Parameterized by Treewidthen_US
dc.typeArticleen_US
Appears in Collections:Research Articles

Files in This Item:
File Description SizeFormat 
Need to add pdf.odt7.99 kBOpenDocument TextView/Open
Show simple item record


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