Connected domination and dominating clique in trapezoid graphs (Q1962037)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Connected domination and dominating clique in trapezoid graphs |
scientific article |
Statements
Connected domination and dominating clique in trapezoid graphs (English)
0 references
24 September 2000
0 references
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.
0 references
trapezoid graphs
0 references
connected dominating set
0 references
connected domination number
0 references
algorithm
0 references
dominating clique
0 references