A Scalable Parallel Algorithm for Turnpike Problem
Fathy, Khaled A.; Bahig, Hazem; Abbas, M.;
Abstract
Given a set of all pairwise distances between points on a line. The Turnpike problem is to reconstruct the positions of those
points. We reduce the running time to generate a set of solution for the turnpike problem by designing a parallel algorithm on a
multicore system in case of the worst case. The algorithm is based on dividing the original problem into many independent subproblems of balanced size. The experimental study shows that our parallel algorithm significantly reduces the running time of
the best practical sequential algorithm. Also, the scalability of the proposed algorithm is linear. Finally, we apply the proposed
algorithm on restriction site mapping of DNA.
points. We reduce the running time to generate a set of solution for the turnpike problem by designing a parallel algorithm on a
multicore system in case of the worst case. The algorithm is based on dividing the original problem into many independent subproblems of balanced size. The experimental study shows that our parallel algorithm significantly reduces the running time of
the best practical sequential algorithm. Also, the scalability of the proposed algorithm is linear. Finally, we apply the proposed
algorithm on restriction site mapping of DNA.
Other data
| Title | A Scalable Parallel Algorithm for Turnpike Problem | Authors | Fathy, Khaled A.; Bahig, Hazem ; Abbas, M. | Keywords | turnpike;parallel algorithm;multi-core;partial-digest | Issue Date | 2018 | Publisher | The Egyptian Knowledge Bank | Journal | JOURNAL OF THE EGYPTIAN MATHEMATICAL SOCIETY (J. Egypt. Math. Soc.) | Volume | 26 | Issue | 1 | Start page | 18 | End page | 26 | DOI | 10.21608/JOEMS.2018.9458 |
Recommend this item
Similar Items from Core Recommender Database
Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.