Connected domination and dominating clique in trapezoid graphs

The class of trapezoid graphs is a subclass of cocomparability graphs and c ontains both the interval graphs and the permutation graphs. In this paper we present an O(n) time algorithm for the minimum cardinality connected dom inating set problem and an O(n + m) time algorithm for the minimum cardinal ity dominating clique problem in trapezoid graphs. Both algorithms require the trapezoid diagram to be given as input. (C) 2000 Elsevier Science B.V. All rights reserved.