Please use this identifier to cite or link to this item:
http://hdl.handle.net/123456789/3453| Title: | Minimum Conflict Free Colouring Parameterized by Treewidth |
| Authors: | Gupta, Naman |
| Keywords: | Conflict free colouring of graphs Parameterized complexity FPT algorithms Treewidth |
| Issue Date: | 2020 |
| Publisher: | Springer Link |
| Citation: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 12016 LNCS, pp. 439-450 |
| 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). |
| Description: | Only IISERM authors are available in the record. |
| URI: | https://link.springer.com/chapter/10.1007%2F978-3-030-39219-2_35 http://hdl.handle.net/123456789/3453 |
| Appears in Collections: | Research Articles |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Need to add pdf.odt | 7.99 kB | OpenDocument Text | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.