AF: Small: RUI:Applications and New Techniques for Exact Parameterized Computation

Texas A&M University, College Station TX

Investigators

Abstract

Efficient algorithms are fundamental to various areas in computer science. This project will study new techniques for designing efficient algorithms for hard combinatorial problems. The interaction between theoretical analysis and practical implementations of such hard problems will be explored. Furthermore, this project will advance the study of algorithms and systems in a minority-serving institution where under-represented students will gain valuable experience in foundational cutting-edge research. More precisely, this project will investigate novel measures for some classical and important NP-hard problems, algebraic techniques for designing exact and parameterized algorithms, and parallel/distributed implementations of exact and parameterized algorithms. The first part is devoted to studying the effects of new measures on designing algorithms for well-known NP-hard problems such as the Boolean Satisfiability Problem. The second part is focused on expanding the power of algebraic techniques to those seemingly difficult problems involving vertex deletion. The last part is to devise a clever way to implement resulting algorithms on a parallel/multi-core machines.