Algorithms and complexity for structured graph classes

许多图问题是NP难的，这意味着即使是非常快的计算机也无法在合理的时间内解决它们。然而，在许多应用中，例如调度和设施定位，情况的结构保证只有某些图会出现。有时，如果事先知道需要处理的图，就有可能为NP难问题构造一个有效的算法。这些意见激发我的研究算法设计和问题的复杂性类的图。我研究类的图形出现在应用程序中，或提供洞察到一个问题的解决方案，并利用它们的属性来设计多项式时间算法或证明这种算法是不可能存在的。我们的目标是了解问题和图形属性之间的相互作用，并找到有效的算法，工作在大类的图形。这项研究增加了关于问题和图形的知识，并具有实际影响，因为图形算法构成了各种应用程序的计算机程序的基础。

Many graph problems are NP-hard, which means that they cannot be solved in a reasonable amount of time even by a very fast computer. However, in many applications, such as scheduling and facility location, the structure of the situation guarantees that only certain graphs will arise. And sometimes it is possible to construct an efficient algorithm for an NP-hard problem if something is known in advance about the graphs that need to be handled. These observations motivate my research in algorithm design and problem complexity in classes of graphs. I study classes of graphs that arise in applications or that give insight into a problem's solution, and make use of their properties to design polynomial time algorithms or to prove that such algorithms are unlikely to exist. The goal is to understand the interplay between problems and graph properties, and to find efficient algorithms that work on large classes of graphs. This research adds to knowledge about problems and graphs, and has practical impact since graph algorithms form the basis of computer programs in diverse applications.**