Combinatorial problems with a view towards algorithms and complexity

所提出的研究包括设计有效的算法，或证明不可能存在这样的算法，对于某些组合问题。尽可能多的研究项目以这样一种方式进行，即为本科生、硕士生、博士生、博士后研究员和年轻同事提供机会。主要涉及三个主题：图的同态、离散时间图过程和图中的支配。其中第一个应用于计算机科学、调度和逻辑。第二个主题，除其他外，涉及一个非常简单但计算困难的病毒或疾病通过网络或人群传播的模型。最后一个主题可以说是离散数学和理论计算机科学中研究得最充分的主题之一。除了本身有趣外，它已被证明是让学生参与研究的绝佳工具。

The proposed research involves the design of efficient algorithms, or a demonstration that no such algorithm is likely to exist, for certain combinatorial problems. As much of the research program as possible is to be carried out in such a way that opportunities are provided for undergraduate students, Master's students, Ph.D. students, post-doctoral fellows, and young colleagues. There are three main topics involved: homomorphisms of graphs, discrete-time graph processes, and domination in graphs. The first of these has applications in computer science, scheduling, and logic. The second topic involves, among other things, a very simple yet computational difficult model of the spread of a virus or disease through a network or population. The final topic is arguably among the most well-studied in discrete mathematics and theoretical computer science. Besides being interesting for its own sake, it has proved to be an excellent vehicle for involving students in research.