Structured graph classes: characterizations, algorithms, and complexity

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

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

Many problems in graph theory are known to be NP-hard, which means that they likely cannot be solved by efficient algorithms. However, it is sometimes possible to construct an efficient algorithm for such a problem, if only a subset of all graphs needs to be considered. The study of particular classes of graphs is usually motivated by theoretical considerations, relationships to previous work, and/or applications. Such graph classes are typically defined in terms of forbidden substructures,  decomposition schemes, vertex orderings, or as intersection (or other) graphs of subsets of a set. The definition usually implies additional properties and structure, which in turn provide clues about how problems may be solved efficiently for those graphs. Most of my research involves characterizing properties of graph classes, and using those properties to design polynomial time algorithms and to prove complexity results, for various problems on structured graphs. The goal is to understand the interplay between problems and graph properties, and to identify relationships that lead to efficient algorithms.

图论中的许多问题都是NP难的，这意味着它们可能无法通过有效的算法来解决。然而，如果只需要考虑所有图的一个子集，有时可以为这样的问题构造一个有效的算法。对特定类图的研究通常是出于理论考虑，与以前工作的关系和/或应用。这样的图类通常被定义在禁止的子结构，分解方案，顶点排序，或作为一个集合的子集的交集（或其他）图。定义通常意味着额外的属性和结构，这反过来又提供了如何有效地解决这些图的问题的线索。我的大部分研究涉及到图形类的特性，并使用这些特性来设计多项式时间算法，并证明复杂性结果，为各种问题的结构图。目标是理解问题和图形属性之间的相互作用，并确定导致有效算法的关系。