Scalable Parallel Exact and Parameterized Algorithms

Project Description: Many exact exponential-time algorithms to NP-hard problems adopt a branch and reduce approach consisting mainly of a depth-first traversal of a search-tree. In this project we study the effectiveness of parallel algorithms that are based on a dynamic decomposition/partitioning of search trees of corresponding sequential algorithms. Both centralized and decentralized computations are explored as well as various dynamic load balancing and task-communication techniques.

PI: Faisal N. Abu-Khzam

Funding: This project has been partially funded by the Lebanese American University.

Publications:

F. N. Abu-Khzam and A. E. Mouawad.
A Decentralized Load Balancing Approach for Parallel Search-Tree Optimization,
in Proceedings, the 13th International Conference on Parallel and Distributed Computing,
Applications and Technologies (PDCAT), 2012:173-178.

F. N. Abu-Khzam, K. Daudjee, A. E. Mouawad and N. Nishimura.
On Scalable Parallel Recursive Backtracking,
Journal of Parallel and Distributed Computing, volume 84, pages 65-75, 2015.

F. N. Abu-Khzam, A. E. Mouawad and K. A. Jahed.
Highly Scalable Parallel Search-Tree Algorithms: The Virtual Topology Approach,
in Proceedings of the IEEE International Conference on Cluster Computing (IEEE Cluster), 2015: 518.

F. N. Abu-Khzam, S. Li, C. Markarian, F. M. auf der Heide and P. Podlipyan.
On the Parameterized Parallel Complexity and the Vertex Cover Problem,
in Proceedings of the 10th conference on Combinatorial Optimization and Applications (COCOA),
Lecture Notes in Computer Science (LNCS 10043), Springer 2016:477-488.

F. N. Abu-Khzam, S. Li, C. Markarian, F. M. auf der Heide and P. Podlipyan.
Modular-Width: an Auxiliary Parameter for Parameterized Parallel Complexity,
in Proceedings of the 11th Intl. Frontiers of Algorithmics Workshop (FAW),
Lecture Notes in Computer Science (LNCS 10336), Springer 2017: 139-150.

F. N. Abu-Khzam, S. Li, C. Markarian, F. M. auf der Heide and P. Podlipyan.
Efficient Parallel Algorithms for Parameterized Problems,
Theoretical Computer Science, volume 786, Pages 2-12, 2019.

Previous publications (from related older projects):

F. N. Abu-Khzam, M. A. Langston and P. Shanbhag.
Scalable Parallel Algorithms for Difficult Combinatorial Problems: A Case Study in Optimization,
in Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Networks,
Innsbruck, Austria, February 17-19, 2004, pages 167-174.

F. N. Abu-Khzam, M. A. Langston, P. Shanbhag and C. T. Symons.
Scalable Parallel Algorithms for FPT Problems,
Algorithmica, volume 45, pages 269-284, 2006.

F. N. Abu-Khzam, M. A. Rizk, D. A. Abdallah and N. F. Samatova.
The Buffered Work-Pool Approach for Search-Tree Based Optimization Algorithms,
in Proceedings of the Seventh International Conference on Parallel Processing and Applied Mathematics, (PPAM-2007),
Lecture Notes in Computer Science, volume 4967, pages 170-179, 2007.