Structured graph classes: characterizations, algorithms, and complexity

点击翻译按钮获取中文摘要

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.