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.