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.