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.