Parameterized Dynamic Problems

Project Description: We study the parameterized complexity of dynamic graph problems when parameterized by the amount of changes made to a dynamic graph/network as well as bounds on the increase/decrease in solutions size.

Publications:

F. N. Abu-Khzam, J. Egan, M. R. Fellows, F. A. Rosamond and P. Shaw. On the Parameterized Complexity of Dynamic Problems with Connectivity Constraints, in Proceedings of the 8th International Conference on Combinatorial Optimization and Applications (COCOA),
Lecture Notes in Computer Science, volume 8881, pages 625-636, 2014.

F. N. Abu-Khzam, J. Egan, M. R. Fellows, F. A. Rosamond and P. Shaw. On the Parameterized Complexity of Dynamic Problems, Theoretical Computer Science, volume 607(3), pages 426-434, 2015.

F. N. Abu-Khzam, S. Cai, J. Egan, P. Shaw and K. Wang. Turbo-charging Dominating Set with an FPT Subroutine: Further Improvements and Experimental Analysis. Proceedings of the 13th annual conference on Theory and Applications of Models of Computation (TAMC),
Lecture Notes in Computer Science (LNCS 10185), Springer 2017: 59-70.

F. N. Abu-Khzam, C. Bazgan and H. Fernau. Parameterized Dynamic Variants of Red-Blue Dominating Set. Poriceedings of the 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM),
Lecture Notes in Computer Science (LNCS 12011), Springer 2020: 236-247.