The parameterised complexity of list problems on graphs of bounded treewidth

被引：4
|
作者：
Meeks, Kitty [1 ,2 ]
Scott, Alexander [1 ]
机构：
[1] Univ Oxford, Math Inst, Radcliffe Observ Quarter, Andrew Wiles Bldg,Woodstock Rd, Oxford OX2 6GG, England
[2] Univ Glasgow, Sch Math & Stat, 15 Univ Gardens, Glasgow G12 8QW, Lanark, Scotland
来源：
INFORMATION AND COMPUTATION | 2016年 / 251卷
关键词：
Parameterised complexity; Bounded treewidth; Graph colouring; List colouring; Hamilton path; NP-COMPLETENESS; CHROMATIC INDEX; TOTAL COLORINGS; EDGE;
D O I：
10.1016/j.ic.2016.08.001
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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). (C) 2016 Elsevier Inc. All rights reserved.
引用
收藏
页码：91 / 103
页数：13
相关论文
共 50 条
  • [11] On the Parameterised Complexity of String Morphism Problems
    Henning Fernau
    Markus L. Schmid
    Yngve Villanger
    Theory of Computing Systems, 2016, 59 : 24 - 51
  • [12] Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
    Bateni, Mohammadhossein
    Hajiaghayi, Mohammadtaghi
    Marx, Daniel
    JOURNAL OF THE ACM, 2011, 58 (05)
  • [13] Computing the Inverse Geodesic Length in Planar Graphs and Graphs of Bounded Treewidth
    Cabello, Sergio
    ACM TRANSACTIONS ON ALGORITHMS, 2022, 18 (02)
  • [14] A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs
    Elisabeth Gassner
    Johannes Hatzl
    Computing, 2008, 82 : 171 - 187
  • [15] A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs
    Gassner, Elisabeth
    Hatzl, Johannes
    COMPUTING, 2008, 82 (2-3) : 171 - 187
  • [16] Finding hamiltonian cycle in graphs of bounded treewidth: Experimental evaluation
    Ziobro M.
    Pilipczuk M.
    ACM Journal of Experimental Algorithmics, 2019, 24 (01):
  • [17] I/O-Efficient Algorithms for Graphs of Bounded Treewidth
    Maheshwari, Anil
    Zeh, Norbert
    ALGORITHMICA, 2009, 54 (03) : 413 - 469
  • [18] On the complexity of some colorful problems parameterized by treewidth
    Fellows, Michael R.
    Fomin, Fedor V.
    Lokshtanov, Daniel
    Rosamond, Frances
    Saurabh, Saket
    Szeider, Stefan
    Thomassen, Carsten
    INFORMATION AND COMPUTATION, 2011, 209 (02) : 143 - 153
  • [19] I/O-Efficient Algorithms for Graphs of Bounded Treewidth
    Anil Maheshwari
    Norbert Zeh
    Algorithmica, 2009, 54 : 413 - 469
  • [20] Steepest ascent can be exponential in bounded treewidth problems
    Cohen, David A.
    Cooper, Martin C.
    Kaznatcheev, Artem
    Wallace, Mark
    OPERATIONS RESEARCH LETTERS, 2020, 48 (03) : 217 - 224
12345