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.