The parameterised complexity of list problems on graphs of bounded treewidthReportar como inadecuado




The parameterised complexity of list problems on graphs of bounded treewidth - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Reference: Scott, A and Meeks, K, (2016). The parameterised complexity of list problems on graphs of bounded treewidth. Information and Computation, 251, 91-103.Citable link to this page:

 

The parameterised complexity of list problems on graphs of bounded treewidth

Abstract: We consider the parameterised complexity of several list problems on graphs, with parameter treewidth or pathwidth. In particular, we show that List Edge Chromatic Number and List Total Chromatic Number are fixed parameter tractable, parameterised by treewidth, whereas List Hamilton Path is W[1]-hard, even parameterised by pathwidth. These results resolve two open questions of Fellows, Fomin, Lokshtanov, Rosamond, Saurabh, Szeider and Thomassen (2011).

Publication status:PublishedPeer Review status:Peer reviewedVersion:Accepted manuscriptDate of acceptance:2017-08-01Notes:© 2016 Elsevier Inc. All rights reserved.

Bibliographic Details

Publisher: Elsevier

Publisher Website: http://www.elsevier.com/

Journal: Information and Computationsee more from them

Publication Website: http://www.journals.elsevier.com/information-and-computation/

Volume: 251

Issue Date: 2016-08

pages:91-103Identifiers

Issn: 1360-2276

Eissn: 1365-3156

Issn: 1090-2651

Uuid: 660414af-e433-459a-a072-ba99ae3c3fd3

Urn: uri:660414af-e433-459a-a072-ba99ae3c3fd3

Pubs-id: 637010

Doi: https://doi.org/10.1016/j.ic.2016.08.001 Item Description

Type: journal-article;

Version: Accepted manuscriptKeywords: Parameterized complexity Bounded treewidth Graph coloring List coloring Hamilton path

Relationships





Autor: Scott, A - Oxford, MPLS, Mathematical Institute Merton College - - - Meeks, K - - - - Bibliographic Details Publisher: Elsevier -

Fuente: https://ora.ox.ac.uk/objects/uuid:660414af-e433-459a-a072-ba99ae3c3fd3



DESCARGAR PDF




Documentos relacionados