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
相关论文
共 38 条
[1]   Crown structures for vertex cover kernelization [J].
Abu-Khzam, Faisal N. ;
Fellows, Michael R. ;
Langston, Michael A. ;
Suters, W. Henry .
THEORY OF COMPUTING SYSTEMS, 2007, 41 (03) :411-430
[2]   Scalable parallel algorithms for FPT problems [J].
Abu-Khzam, Faisal N. ;
Langston, Michael A. ;
Shanbhag, Pushkar ;
Symons, Christopher T. .
ALGORITHMICA, 2006, 45 (03) :269-284
[3]  
Abu-Khzam FN, 2005, I C COMP SYST APPLIC
[4]   Efficient parallel algorithms for parameterized problems [J].
Abu-Khzam, Faisal N. ;
Li, Shouwei ;
Markarian, Christine ;
Heide, Friedhelm Meyer auf der ;
Podlipyan, Pavel .
THEORETICAL COMPUTER SCIENCE, 2019, 786 :2-12
[5]   On the complexity of multi-parameterized cluster editing [J].
Abu-Khzam, Faisal N. .
Journal of Discrete Algorithms, 2017, 45 :26-34
[6]   Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity [J].
Abu-Khzam, Faisal N. ;
Li, Shouwei ;
Markarian, Christine ;
Heide, Friedhelm Meyer auf der ;
Podlipyan, Pavel .
FRONTIERS IN ALGORITHMICS, FAW 2017, 2017, 10336 :139-150
[7]   On scalable parallel recursive backtracking [J].
Abu-Khzam, Faisal N. ;
Daudjee, Khuzaima ;
Mouawad, Amer E. ;
Nishimura, Naomi .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2015, 84 :65-75
[8]  
Abu-Khzam FN, 2010, LECT NOTES COMPUT SC, V6213, P136, DOI 10.1007/978-3-642-14553-7_15
[9]  
AbuKhzam F.N, 2016, P COMB OPT APPL, P477, DOI [10.1007/978-3-319-48749-6_35, DOI 10.1007/978-3-319-48749-6_35]
[10]  
Alon N., 1994, Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, P326, DOI 10.1145/195058.195179
1234