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

有效的算法是计算机科学各个领域的基础。本计画将研究设计有效演算法解决组合难题的新技术。将探讨这些难题的理论分析和实际实施之间的相互作用。此外，该项目将推进算法和系统在少数民族服务机构的研究，其中代表性不足的学生将获得基础前沿研究的宝贵经验。 更确切地说，这个项目将研究一些经典和重要的NP-难问题的新措施，设计精确和参数化算法的代数技术，以及精确和参数化算法的并行/分布式实现。第一部分是专门研究的影响，新的措施设计算法的著名的NP难问题，如布尔可满足性问题。第二部分是集中在扩大的权力，代数技术，以那些看似困难的问题，涉及顶点删除。最后一部分是设计一种巧妙的方法来实现并行/多核机器上的算法。

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.