TY - GEN
T1 - On the relative significance of kernelization versus branching for parallel FPT implementations
AU - Hagan, Ronald D.
AU - Philips, Charles A.
AU - Wang, Kai
AU - Rogers, Gary L.
AU - Lowcay, Callum
AU - Langston, Michael A.
N1 - We investigate the relative significance of kernelization versus branching for parallel FPT implementations.
PY - 2013
Y1 - 2013
N2 - We investigate the relative significance of kernelization versus branching for parallel FPT implementations. Using the well-known vertex cover problem as a familiar example, we build and experiment with a testbed of five different classes of difficult graphs. For some, we find that kernelization alone obviates the need for parallelism. For others, we show that kernelization and branching work in synergy to produce efficient implementations. And yet for others, kernelization fails completely, leaving branching to solve the entire problem. Structural graph properties are studied in an effort to explicate this trichotomy. The NP-completeness of vertex cover makes scalability an extreme challenge. We mainly employ Hopper, named after the famous computing pioneer Admiral Grace Murray Hopper. The Hopper platform is currently one of the world's fastest supercomputers.
AB - We investigate the relative significance of kernelization versus branching for parallel FPT implementations. Using the well-known vertex cover problem as a familiar example, we build and experiment with a testbed of five different classes of difficult graphs. For some, we find that kernelization alone obviates the need for parallelism. For others, we show that kernelization and branching work in synergy to produce efficient implementations. And yet for others, kernelization fails completely, leaving branching to solve the entire problem. Structural graph properties are studied in an effort to explicate this trichotomy. The NP-completeness of vertex cover makes scalability an extreme challenge. We mainly employ Hopper, named after the famous computing pioneer Admiral Grace Murray Hopper. The Hopper platform is currently one of the world's fastest supercomputers.
KW - Fixed-parameter tractability
KW - High performance computation
KW - Kernelization and branching
KW - Parallel algorithms and implementations
UR - https://www.scopus.com/pages/publications/84875554225
U2 - 10.2316/P.2013.795-049
DO - 10.2316/P.2013.795-049
M3 - Conference article
SN - 9780889869431
T3 - IASTED Multiconferences - Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Networks, PDCN 2013
SP - 621
EP - 627
BT - IASTED Multiconferences - Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Networks, PDCN 2013
T2 - 11th IASTED International Conference on Parallel and Distributed Computing and Networks, PDCN 2013
Y2 - 11 February 2013 through 13 February 2013
ER -