Graph classes: Structure, algorithms, and complexity

图类：结构、算法和复杂性

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

Many graph problems are known to be NP-hard, which means that they likely cannot be solved in a reasonable amount of time even by a fast computer. However, it is sometimes possible to construct an efficient algorithm for such a problem if something is known in advance about the kinds of graphs that need to be handled. In my research, I consider graph classes 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 an algorithm is unlikely to exist. The goal is to understand the interplay between problems and graph properties, and to identify relationships between graph classes and problems that lead to efficient algorithms.

已知许多图形问题是NP-HARD，这意味着即使快速计算机也可能无法在合理的时间内解决它们。但是，如果事先知道需要处理的各种图表，则有时可以为此问题构造有效的算法。在我的研究中，我考虑了在应用程序中出现的图形类别或能够深入了解问题的解决方案，并利用其属性来设计多项式时间算法，或者证明这种算法不太可能存在。目的是了解问题和图形属性之间的相互作用，并确定图形类别与导致有效算法的问题之间的关系。