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 条
  • [31] Chordal Editing is Fixed-Parameter Tractable
    Cao, Yixin
    Marx, Daniel
    31ST INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2014), 2014, 25 : 214 - 225
  • [32] On the fixed-parameter enumerability of cluster editing
    Damaschke, P
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2005, 3787 : 283 - 294
  • [33] Jungles, bundles, and fixed-parameter tractability
    Fomin, Fedor V.
    Pilipczuk, Michal
    PROCEEDINGS OF THE TWENTY-FOURTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA 2013), 2013, : 396 - 413
  • [34] Unit Interval Editing Is Fixed-Parameter Tractable
    Cao, Yixin
    AUTOMATA, LANGUAGES, AND PROGRAMMING, PT I, 2015, 9134 : 306 - 317
  • [35] Fixed-Parameter Algorithms for Cluster Vertex Deletion
    Falk Hüffner
    Christian Komusiewicz
    Hannes Moser
    Rolf Niedermeier
    Theory of Computing Systems, 2010, 47 : 196 - 217
  • [36] Sparse Integer Programming Is Fixed-Parameter Tractable
    Eisenbrand, Friedrich
    Hunkenschroeder, Christoph
    Klein, Kim-Manuel
    Koutecky, Martin
    Levin, Asaf
    Onn, Shmuel
    MATHEMATICS OF OPERATIONS RESEARCH, 2024,
  • [37] A fixed-parameter algorithm for dominance drawings of DAGs
    Ortali, Giacomo
    Tollis, Ioannis G.
    THEORETICAL COMPUTER SCIENCE, 2024, 1020
  • [38] Fixed-parameter tractable generalizations of cluster editing
    Damaschke, Peter
    ALGORITHMS AND COMPLEXITY, PROCEEDINGS, 2006, 3998 : 344 - 355
  • [39] Fixed-parameter algorithms for graph constraint logic *,**
    Hatanaka, Tatsuhiko
    Hommelsheim, Felix
    Ito, Takehiro
    Kobayashi, Yusuke
    Muehlenthaler, Moritz
    Suzuki, Akira
    THEORETICAL COMPUTER SCIENCE, 2023, 959
  • [40] Fixed-Parameter Algorithms for Closed World Reasoning
    Lackner, Martin
    Pfandler, Andreas
    20TH EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE (ECAI 2012), 2012, 242 : 492 - 497
12345