Minimum Conflict Free Colouring Parameterized by Treewidth
| dc.contributor.author | Gupta, Naman | |
| dc.date.accessioned | 2020-12-30T10:03:19Z | |
| dc.date.available | 2020-12-30T10:03:19Z | |
| dc.date.issued | 2020 | |
| dc.description | Only IISERM authors are available in the record. | |
| dc.description.abstract | Conflict 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.identifier.citation | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 12016 LNCS, pp. 439-450 | en_US |
| dc.identifier.other | 10.1007/978-3-030-39219-2_35 | |
| dc.identifier.uri | https://link.springer.com/chapter/10.1007%2F978-3-030-39219-2_35 | |
| dc.identifier.uri | http://hdl.handle.net/123456789/3453 | |
| dc.language.iso | en | en_US |
| dc.publisher | Springer Link | en_US |
| dc.subject | Conflict free colouring of graphs | en_US |
| dc.subject | Parameterized complexity | en_US |
| dc.subject | FPT algorithms | en_US |
| dc.subject | Treewidth | en_US |
| dc.title | Minimum Conflict Free Colouring Parameterized by Treewidth | en_US |
| dc.type | Article | en_US |