A Brief Survey of Fixed-Parameter Parallelism

被引：2
|
作者：
Abu-Khzam, Faisal N. [1 ]
Al Kontar, Karam [1 ]
机构：
[1] Lebanese Amer Univ, Dept Comp Sci & Math, Beirut 11022801, Lebanon
来源：
ALGORITHMS | 2020年 / 13卷 / 08期
关键词：
fixed-parameter parallelism; parameterized complexity; parallel computing; ALGORITHMS;
D O I：
10.3390/a13080197
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
This paper provides an overview of the field of parameterized parallel complexity by surveying previous work in addition to presenting a few new observations and exploring potential new directions. In particular, we present a general view of how knownFPTtechniques, such as bounded search trees, color coding, kernelization, and iterative compression, can be modified to produce fixed-parameter parallel algorithms.
引用
收藏
页数：16
相关论文
共 50 条
  • [1] Fixed-parameter tractability
    Samer, Marko
    Szeider, Stefan
    Frontiers in Artificial Intelligence and Applications, 2009, 185 (01) : 425 - 454
  • [2] Scheduling and fixed-parameter tractability
    Mnich, Matthias
    Wiese, Andreas
    MATHEMATICAL PROGRAMMING, 2015, 154 (1-2) : 533 - 562
  • [3] A Fixed-Parameter Perspective on #BIS
    Radu Curticapean
    Holger Dell
    Fedor Fomin
    Leslie Ann Goldberg
    John Lapinskas
    Algorithmica, 2019, 81 : 3844 - 3864
  • [4] Invitation to fixed-parameter algorithms
    Thilikos, Dimitrios M.
    COMPUTER SCIENCE REVIEW, 2007, 1 (02) : 103 - 104
  • [5] Fixed-parameter algorithms in phylogenetics
    Gramm, Jens
    Nickelsen, Arfst
    Tantau, Till
    COMPUTER JOURNAL, 2008, 51 (01): : 79 - 101
  • [6] Scheduling and fixed-parameter tractability
    Matthias Mnich
    Andreas Wiese
    Mathematical Programming, 2015, 154 : 533 - 562
  • [7] A Fixed-Parameter Perspective on #BIS
    Curticapean, Radu
    Dell, Holger
    Fomin, Fedor
    Goldberg, Leslie Ann
    Lapinskas, John
    ALGORITHMICA, 2019, 81 (10) : 3844 - 3864
  • [8] Fixed-parameter complexity of λ-labelings
    Fiala, J
    Kloks, T
    Kratochvíl, J
    DISCRETE APPLIED MATHEMATICS, 2001, 113 (01) : 59 - 72
  • [9] Chordal Deletion is Fixed-Parameter Tractable
    Dániel Marx
    Algorithmica, 2010, 57 : 747 - 768
  • [10] Rotation distance is fixed-parameter tractable
    Cleary, Sean
    John, Katherine St.
    INFORMATION PROCESSING LETTERS, 2009, 109 (16) : 918 - 922
12345