Algorithmic graph theory

本研究建议的主要目标是设计一些图形类的有效算法和研究它们的结构。我们感兴趣的图类的例子是弦图，弱弦图，完美可序图，完美图和2-可分图。在大多数情况下，这些图的结构可以用来设计有效的识别和优化算法。我们将处理这些问题，鉴于最近的两个发展：强大的算法和认证算法。一个图类C的算法是鲁棒的，如果当输入图在该类中时它给出了正确的解;如果输入不在C中，那么算法仍然产生正确的解或回答输入不在C中。认证算法是一种生成证书的算法，每个输出都证明它没有被实现错误所破坏。例如，用于识别平面图G的证明算法产生G的平面嵌入或两个Kuratowski图之一。这两个概念为算法的设计提供了新的见解。

The main objectives of this research proposal are the design of efficient algorithms for a number of graph classes and the study of their structures. Examples of graph classes we are interested in are chordal graphs, weakly chordal graphs, perfectly orderable graphs, perfect graphs, and 2-divisible graphs. These graphs in most cases have structures that can be exploited to design efficient algorithms for recognition and optimization. We will approach these problems in the view of two recent developments: robust algorithms and certifying algorithms. An algorithm for a graph class C is robust if it gives the correct solution when the input graph is in the class; if the input is not in C, then the algorithm either still produces a correct solution or answers that the input is not in C. A certifying algorithm is one that produces a certificate with each output that proves that it has not been compromised by an implementation bug. For example, a certifying algorithm for recognizing a planar graph G produces either a planar embedding of G, or one of the two Kuratowski graphs. These two notions provide new and fresh insights into the design of algorithms.