Connected domination and dominating clique in trapezoid graphs

DOI10.1016/S0166-218X(99)00127-4MaRDI QIDQ1962037zbMATH OpenFDO

Authors Ekkehard Köhler

Publication date 24 September 2000

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0166-218X(99)00127-4

zbMATH Keywords

algorithmconnected dominating setconnected domination numberdominating cliquetrapezoid graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85)

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.

Recommendations

• Efficient algorithms for the minimum connected domination on trapezoid graphs
• scientific article; zbMATH DE number 1696629
• Trapezoid graphs and generalizations, geometry and algorithms
• scientific article; zbMATH DE number 992410
• Parallel algorithms for the domination problems in trapezoid graphs

Cites work

• Domination on Cocomparability Graphs
• Dominations in trapezoid graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• scientific article; zbMATH DE number 4063148 (Why is no real title available?)
• Some Efficient Algorithms for Permutation Graphs
• Trapezoid graphs and generalizations, geometry and algorithms
• Trapezoid graphs and their coloring
• Weighted irredundance of interval graphs.

Cited in

(8)

• Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs
• The hub number of co-comparability graphs
• scientific article; zbMATH DE number 1696629 (Why is no real title available?)
• scientific article; zbMATH DE number 992410 (Why is no real title available?)
• The recognition of triangle graphs
• Fine-grained complexity of multiple domination and dominating patterns in sparse graphs
• Fine-grained classification of detecting dominating patterns
• Efficient algorithms for the minimum connected domination on trapezoid graphs

This page was built for publication: Connected domination and dominating clique in trapezoid graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1962037)