Connected domination and steiner set on asteroid triple-free graphs

An asteroidal triple is a set of three independent vertices such that between any two of them there exists a path that avoids the neighbourhood of the third. Graphs that do not contain an asteroidal triple are called asteroidal triple-free (AT-free) graphs. AT-free graphs strictly contain the well-known class of cocomparability graphs, and are not necessarily perfect. We present efficient polynomial-time algorithms for the minimum cardinality connected dominating set problem and the Steiner set problem on AT-free graphs. These results, in addition to solving these problems on this large class of graphs, also strengthen the conjecture of White, et. al. [9] that these two problems are algorithmically closely related.