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.