Connected domination and dominating clique in trapezoid graphs

Connected domination and dominating clique in trapezoid graphs

0.00 Avg rating0 Votes
Article ID: iaor20012900
Country: Netherlands
Volume: 99
Issue: 1/3
Start Page Number: 91
End Page Number: 110
Publication Date: Feb 2000
Journal: Discrete Applied Mathematics
Authors:
Abstract:

The class of trapezoid graphs is a subclass of cocomparability graphs and contains both the interval graphs and the permutation graphs. In this paper we present an O(n) time algorithm for the minimum cardinality connected dominating set problem and an O(n+m) time algorithm for the minimum cardinality dominating clique problem in trapezoid graphs. Both algorithms require the trapezoid diagram to be given as input.

Reviews

Required fields are marked *. Your email address will not be published.