Grant: Discovery Grants Program - Individual

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.