ICBAIE 2020

Welcome Prof. Faisal N. Abu-Khzam, ​from Computer Science and Mathematics Department, Lebanese to be Keynote Speaker!

Prof. Faisal N. Abu-Khzam, IEEE Senior Member, Computer Science and Mathematics Department, Lebanese  American University, Lebanon (click) Research Area: Exact and Parameterized Algorithms, High Performance Computing, Combinatorial Optimization, Graph Theory and Computational Biology

Title: Efficient Parallel Algorithms for Parameterized Problems

Abstract: A parameterized problem is fixed-parameter parallelizable (FPP) if it can be solved in O(f(k)⋅(logN)α) time using O(g(k)⋅Nβ) processors, where N is the input size, k is the parameter and g are arbitrary computable functions, and α, β are constants independent of N and k. We re-examine the k-vertex cover problem from a parameterized parallel complexity standpoint and present a parallel algorithm that outperforms the previous known algorithm: using O(m) instead of O(n²) processors, the running time improves from O(kk) to O(k³logn+1.2738k), where n and m are the number of vertices and edges of the input graph, respectively. This is achieved by first showing that vertex cover kernelization that is based on crown decomposition is in FPP as well. Finally, we consider the use of the recently introduced modular-width parameter. In particular, we show that the weighted maximum clique problem is FPP when parameterized by this auxiliary parameter.