Scalable parallel algorithms for FPT problems

被引:47
作者
Abu-Khzam, Faisal N. [1 ]
Langston, Michael A.
Shanbhag, Pushkar
Symons, Christopher T.
机构
[1] Lebanese Amer Univ, Div Math & Comp Sci, Beirut, Lebanon
[2] Univ Tennessee, Dept Comp Sci, Knoxville, TN 37996 USA
基金
欧盟地平线“2020”;
关键词
algorithm design; parallel computing; optimization; load balancing; applications;
D O I
10.1007/s00453-006-1214-1
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
Algorithmic methods based on the theory of fixed-parameter tractability are combined with powerful computational platforms to launch systematic attacks on combinatorial problems of significance. As a case study, optimal solutions to very large instances of the NP-hard vertex cover problem are computed. To accomplish this, an efficient sequential algorithm and various forms of parallel algorithms are devised, implemented, and compared. The importance of maintaining a balanced decomposition of the search space is shown to be critical to achieving scalability. Target problems need only be amenable to reduction and decomposition. Applications in high throughput computational biology are also discussed.
引用
收藏
页码:269 / 284
页数:16
相关论文
共 27 条
[1]  
ABUKHZAM FN, 2004, IN PRESS P WORKSH AL
[2]  
ABUKHZAM FN, CLUSTALXP
[3]  
ABUKHZAM FN, 2003, THESIS U TENNESSEE
[4]  
AGRAWAL S, 2003, NETSOLVE PAST PRESEN
[5]  
[Anonymous], 1997, APPROXIMATION ALGORI
[6]  
BALDWIN NE, 2004, IN PRESS P IEEE INT
[7]   NONDETERMINISM WITHIN P [J].
BUSS, JF ;
GOLDSMITH, J .
SIAM JOURNAL ON COMPUTING, 1993, 22 (03) :560-572
[8]  
CATTELL K, 1994, P INT WORKSH ORD ALG, P86
[9]   Solving large FPT problems on coarse-grained parallel machines [J].
Cheetham, J ;
Dehne, F ;
Rau-Chaplin, A ;
Stege, U ;
Taillon, PJ .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2003, 67 (04) :691-706
[10]   Vertex Cover: Further observations and further improvements [J].
Chen, J ;
Kanj, IA ;
Jia, WJ .
JOURNAL OF ALGORITHMS, 2001, 41 (02) :280-301