Connected domination and dominating clique in trapezoid graphs (Q1962037): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3797233 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Trapezoid graphs and their coloring / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Trapezoid graphs and generalizations, geometry and algorithms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some Efficient Algorithms for Permutation Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Domination on Cocomparability Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Dominations in trapezoid graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Weighted irredundance of interval graphs. / rank | |||
Normal rank |
Latest revision as of 12:29, 29 May 2024
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