Algorithms and complexity for structured graph classes

结构化图类的算法和复杂性

• 批准号: RGPIN-2016-04849
• 负责人: Stewart, Lorna
• 金额: $ 1.6万
• 依托单位: University of Alberta
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750520
• 关键词: Algorithms; complexity; structured; graph; classes

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.

许多图形问题都是NP硬化，这意味着即使是非常快的计算机，也无法在合理的时间内解决它们。但是，在许多应用程序（例如调度和设施位置）中，情况的结构可以保证只会出现某些图。有时，如果事先知道需要处理的图表，则有可能为NP问题构造有效的算法。这些观察结果激发了我在算法设计和图形类别中问题复杂性方面的研究。我研究了在应用中出现的图形或能够深入了解问题解决方案的图表，并利用其属性来设计多项式时间算法或证明这种算法不太可能存在。目的是了解问题和图形属性之间的相互作用，并找到在大量图上使用的有效算法。这项研究增加了有关问题和图形的知识，并且具有实际影响，因为图算法构成了不同应用程序中计算机程序的基础。