Combinatorial problems from the perspective of algorithms and complexity

我们建议继续我们的长期研究计划，包括图着色和同态的研究，这在调度和物流中有应用，支配集，这在定位资源和网络中有应用，以及离散时间图过程，它的应用范围从网络安全到管道网络的自动清洗。所提出的研究的一个重要特点是，尽可能多地以这样一种方式进行，即为本科生、研究生、博士后和青年研究人员创造发展机会。我们要研究的所有主题都有一个共同的特点，那就是时间。我们正在寻找问题的计算效率的解决方案（由计算机在合理的时间内解决），或者证明不可能存在这样的解决方案。当出现后一种情况时，我们寻找可以有效找到的近似解或允许这种解的问题的特殊情况。

We propose a continuation of our long-term research program involving the study of graph colourings and homomorphisms, which have applications in scheduling and logistics, dominating sets, which have applications in locating resources and networks, and discrete-time graph processes, which have applications ranging from network security to automated cleaning of networks of pipes. An important feature of the study proposed is that as much of it as possible is to be carried out in such a way that development opportunities for undergraduate students, graduate students, post-doctoral fellows and young researchers are generated. A common feature to all of the topics we propose to study is time. We are looking for either computationally efficient solutions to the problems in question (solvable by a computer in a reasonable amount of time), or a demonstration that no such solution is likely to exist. When the latter situation arises, we look for approximate solutions that can be found efficiently or special cases of the problem that admit such solutions.