PARAMETERIZED COMPLEXITY FOR GRAPH LAYOUT PROBLEMS

被引：0
|
作者：
Serna, Maria [1 ]
Thilikos, Dimitrios M. [1 ]
机构：
[1] Politecn Univ Catalunya, Dept Languages & Comp Syst, Campus Nord Edifici,C Jodi Girona 1-3, E-08034 Barcelona, Spain
来源：
BULLETIN OF THE EUROPEAN ASSOCIATION FOR THEORETICAL COMPUTER SCIENCE | 2005年 / 86期
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Layout problems form a family of problems which seem to be difficult to solve efficiently. In the present column, D. Thilikos and M. Serna address the parameterized complexity of graph layout problems. They survey the unifying methodologies yielding fixed parameter tractability when the layout measure is taken as parameter and collect a series of open questions related to its parameterized complexity.
引用
收藏
页码：41 / 65
页数：25
相关论文
共 50 条
  • [1] Graph Layout Problems Parameterized by Vertex Cover
    Fellows, Michael R.
    Lokshtanov, Daniel
    Misra, Neeldhara
    Rosamond, Frances A.
    Saurabh, Saket
    ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2008, 5369 : 294 - +
  • [2] On the parameterized complexity of multiple-interval graph problems
    Fellows, Michael R.
    Hermelin, Danny
    Rosamond, Frances
    Vialette, Stephane
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (01) : 53 - 61
  • [3] Extension of Some Edge Graph Problems: Standard and Parameterized Complexity
    Casel, Katrin
    Fernau, Henning
    Ghadikolaei, Mehdi Khosravian
    Monnot, Jerome
    Sikora, Florian
    FUNDAMENTALS OF COMPUTATION THEORY, FCT 2019, 2019, 11651 : 185 - 200
  • [4] Preprocessing complexity for some graph problems parameterized by structural parameters
    Lafond, Manuel
    Luo, Weidong
    DISCRETE APPLIED MATHEMATICS, 2025, 371 : 46 - 59
  • [5] Preprocessing complexity for some graph problems parameterized by structural parameters
    Lafond, Manuel
    Luo, Weidong
    XII LATIN-AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, LAGOS 2023, 2023, 224 : 130 - 139
  • [6] The Parameterized Complexity of Graph Cyclability
    Golovach, Petr A.
    Kaminski, Marcin
    Maniatis, Spyridon
    Thilikos, Dimitrios M.
    ALGORITHMS - ESA 2014, 2014, 8737 : 492 - 504
  • [7] Parameterized Complexity of Graph Burning
    Yasuaki Kobayashi
    Yota Otachi
    Algorithmica, 2022, 84 : 2379 - 2393
  • [8] Parameterized Complexity of Graph Burning
    Kobayashi, Yasuaki
    Otachi, Yota
    ALGORITHMICA, 2022, 84 (08) : 2379 - 2393
  • [9] THE PARAMETERIZED COMPLEXITY OF GRAPH CYCLABILITY
    Golovach, Petr A.
    Kaminski, Marcin
    Maniatis, Spyridon
    Thilikos, Dimitrios M.
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2017, 31 (01) : 511 - 541
  • [10] Extension of some edge graph problems: Standard, parameterized and approximation complexity
    Casel, Katrin
    Fernau, Henning
    Ghadikolaei, Mehdi Khosravian
    Monnot, Jerome
    Sikora, Florian
    DISCRETE APPLIED MATHEMATICS, 2023, 340 : 183 - 201
12345