Connected domination and dominating clique in trapezoid graphs
type: Item
instance of: scholarly article
title: Connected domination and dominating clique in trapezoid graphs
zbMATH Open document ID: 0944.05072
DOI: 10.1016/S0166-218X(99)00127-4
author: Ekkehard Köhler
published in: Discrete Applied Mathematics
publication date: 2000-09-24T00:00:00Z
review text: The class of trapezoid graphs is defined as the intersection graphs of a collection of trapezoids. A set of vertices that dominates the graph and induces a connected graph is a connected dominating set. The smallest set is called the connected domination number for the graph. It is known that this problem is NP-hard. The author develops an \(O(n)\) algorithm for finding a minimum connected dominating set in a trapezoid graph. If a trapezoid graph has a dominating clique, the author develops an \(O(m+n)\) algorithm for finding such a clique. This algorithm depends on the fact that if such a clique exists, then it has cardinality at most four.
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1395006
zbMATH Keywords: trapezoid graphs
zbMATH Keywords: connected dominating set
zbMATH Keywords: connected domination number
zbMATH Keywords: algorithm
zbMATH Keywords: dominating clique
reviewed by: Ortrud R. Oellermann
MaRDI profile type: Publication
cites work: Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
cites work: Q3797233
cites work: Trapezoid graphs and their coloring
cites work: Trapezoid graphs and generalizations, geometry and algorithms
cites work: Some Efficient Algorithms for Permutation Graphs
cites work: Domination on Cocomparability Graphs
cites work: Dominations in trapezoid graphs
cites work: Weighted irredundance of interval graphs.
description: scientific article; zbMATH DE number 1395006