@inproceedings{14d7ff3a89f84082a5adacc7bcddaba0,
title = "Finding Hamiltonian paths in tournaments on clusters - A provably communication-efficient approach",
abstract = "This paper presents a general methodology for the communication efficient parallelization of graph algorithms using divide-and-conquer approach and shows that this class of problems can be solved in cluster environments with good communication efficiency. Specifically, the first practical parallel algorithm, based onEREW BSP model, for finding Hamiltonian paths in tournaments is presented. For all commercially available parallel computing environments, this algorithm uses only (3logp+1) communication supersteps, which is independent of the tournament size, and can reuse the existing linear-time algorithm in sequential setting. Experiments have been carried out on a Linux cluster of 32 Sun Ultra5 computers and SGI Origin 2000 with 32 R10000 processors, using MPI. The algorithm performance on Linux Cluster reaches 75\% of the performance on SGI Origin 2000 when the tournament size is about one million.",
keywords = "BSP, Cluster computing, MPI, Tournament",
author = "Huang, \{Chun Hsi\} and Xin He",
note = "Publisher Copyright: {\textcopyright} 2001 ACM.; 2001 ACM Symposium on Applied Computing, SAC 2001 ; Conference date: 11-03-2001 Through 14-03-2001",
year = "2001",
month = mar,
day = "1",
doi = "10.1145/372202.372459",
language = "English",
isbn = "1581132875",
series = "Proceedings of the ACM Symposium on Applied Computing",
publisher = "Association for Computing Machinery ",
pages = "549--553",
booktitle = "Proceedings of the 2001 ACM Symposium on Applied Computing, SAC 2001",
address = "United States",
}