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 条
  • [31] Parameterized Complexity of Superstring Problems
    Bliznets, Ivan
    Fomin, Fedor V.
    Golovach, Petr A.
    Karpov, Nikolay
    Kulikov, Alexander S.
    Saurabh, Saket
    ALGORITHMICA, 2017, 79 (03) : 798 - 813
  • [32] Parameterized Complexity of Superstring Problems
    Ivan Bliznets
    Fedor V. Fomin
    Petr A. Golovach
    Nikolay Karpov
    Alexander S. Kulikov
    Saket Saurabh
    Algorithmica, 2017, 79 : 798 - 813
  • [33] Parameterized graph separation problems
    Marx, D
    PARAMETERIZED AND EXACT COMPUTATION, PROCEEDINGS, 2004, 3162 : 71 - 82
  • [34] On the parameterized complexity of dynamic problems
    Abu-Khzam, Faisal N.
    Egan, Judith
    Fellows, Michael R.
    Rosamond, Frances A.
    Shaw, Peter
    THEORETICAL COMPUTER SCIENCE, 2015, 607 : 426 - 434
  • [35] Parameterized Graph Cleaning Problems
    Marx, Daniel
    Schlotter, Ildiko
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2008, 5344 : 287 - 299
  • [36] Parameterized graph separation problems
    Marx, D
    THEORETICAL COMPUTER SCIENCE, 2006, 351 (03) : 394 - 406
  • [37] Parameterized graph cleaning problems
    Marx, Daniel
    Schlotter, Ildiko
    DISCRETE APPLIED MATHEMATICS, 2009, 157 (15) : 3258 - 3267
  • [38] On the Parallel Parameterized Complexity of the Graph Isomorphism Problem
    Das, Bireswar
    Enduri, Murali Krishna
    Reddy, I. Vinod
    WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2018, 2018, 10755 : 252 - 264
  • [39] COMPLEXITY OF FACILITIES LAYOUT PROBLEMS
    BLOCK, TE
    MANAGEMENT SCIENCE, 1979, 25 (03) : 280 - 285
  • [40] On the parameterized complexity of exact satisfiability problems
    Kneis, J
    Mölle, D
    Richter, S
    Rossmanith, P
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2005, PROCEEDINGS, 2005, 3618 : 568 - 579
12345