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 条
  • [21] The Parameterized Complexity of Geometric Graph Isomorphism
    Arvind, Vikraman
    Rattan, Gaurav
    PARAMETERIZED AND EXACT COMPUTATION, IPEC 2014, 2014, 8894 : 51 - 62
  • [22] The Parameterized Complexity of Geometric Graph Isomorphism
    Arvind, V.
    Rattan, Gaurav
    ALGORITHMICA, 2016, 75 (02) : 258 - 276
  • [23] GRAPH LAYOUT PROBLEMS
    DIAZ, J
    LECTURE NOTES IN COMPUTER SCIENCE, 1992, 629 : 14 - 23
  • [24] The parameterized complexity of counting problems
    Flum, J
    Grohe, M
    FOCS 2002: 43RD ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2002, : 538 - 547
  • [25] Counting Problems in Parameterized Complexity
    Zhang, Chihao
    Chen, Yijia
    TSINGHUA SCIENCE AND TECHNOLOGY, 2014, 19 (04) : 410 - 420
  • [26] Counting Problems in Parameterized Complexity
    Chihao Zhang
    Yijia Chen
    TsinghuaScienceandTechnology, 2014, 19 (04) : 410 - 420
  • [27] On the Parameterized Complexity of Reconfiguration Problems
    Mouawad, Amer E.
    Nishimura, Naomi
    Raman, Venkatesh
    Simjour, Narges
    Suzuki, Akira
    ALGORITHMICA, 2017, 78 (01) : 274 - 297
  • [28] The parameterized complexity of counting problems
    Flum, J
    Grohe, M
    SIAM JOURNAL ON COMPUTING, 2004, 33 (04) : 892 - 922
  • [29] Parameterized complexity of geometric problems
    Giannopoulos, Panos
    Knauer, Christian
    Whitesides, Sue
    COMPUTER JOURNAL, 2008, 51 (03): : 372 - 384
  • [30] On the Parameterized Complexity of Reconfiguration Problems
    Amer E. Mouawad
    Naomi Nishimura
    Venkatesh Raman
    Narges Simjour
    Akira Suzuki
    Algorithmica, 2017, 78 : 274 - 297
12345