×

Connected domination and dominating clique in trapezoid graphs. (English) Zbl 0944.05072

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.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] K. Arvind, H. Breu, M.-S. Chang, D.G. Kirkpatrick, F.-Y. Lee, Y.D. Liang, K. Madhukar, C. Pandu Rangan, A. Srinivasan, Efficient algorithms in cocomparability graphs and trapezoid graphs, manuscript.; K. Arvind, H. Breu, M.-S. Chang, D.G. Kirkpatrick, F.-Y. Lee, Y.D. Liang, K. Madhukar, C. Pandu Rangan, A. Srinivasan, Efficient algorithms in cocomparability graphs and trapezoid graphs, manuscript.
[2] M.-S. Chang, Efficient algorithms for the domination problems on interval and circular-arc graphs, SIAM J. Comput., in press.; M.-S. Chang, Efficient algorithms for the domination problems on interval and circular-arc graphs, SIAM J. Comput., in press.
[3] F.H.K. Cheah, A recognition algorithm for II-graphs, Ph. D. Thesis, Department of Computer Science, University of Toronto, 1990.; F.H.K. Cheah, A recognition algorithm for II-graphs, Ph. D. Thesis, Department of Computer Science, University of Toronto, 1990.
[4] Corneil, D.; Kamula, P., Extensions of permutation and interval graphs, Proceedings of the 18th Southeast. Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, 1987; Congr. Numer., 58, 267-275 (1987) · Zbl 0652.05055
[5] Dagan, I.; Golumbic, M. C.; Pinter, R. Y., Trapezoid Graphs and their Coloring, Discrete Appl. Math., 21, 35-46 (1988) · Zbl 0658.05067
[6] S. Felsner, R. Müller, L. Wernisch, Trapezoid graphs and generalizations, geometry and algorithms, Proceedings of the fourth Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, Vol. 824, Springer, Berlin, 1994, pp. 143-154.; S. Felsner, R. Müller, L. Wernisch, Trapezoid graphs and generalizations, geometry and algorithms, Proceedings of the fourth Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, Vol. 824, Springer, Berlin, 1994, pp. 143-154.
[7] Ibarra, O. H.; Zheng, Q., Some efficient algorithms for permutation graphs, J. Algorithms, 16, 453-469 (1994) · Zbl 0804.68102
[8] Kratsch, D.; Stewart, L., Domination in cocomparability graphs, SIAM J. Discrete Math., 6, 400-417 (1993) · Zbl 0780.05032
[9] Liang, Y. D., Domination in trapezoid graphs, Informat. Process. Lett., 52, 309-315 (1994) · Zbl 0938.68925
[10] Liang, Y. D., Steiner set and connected domination in trapezoid graphs, Inform. Process. Lett., 56, 101-108 (1995)
[11] C. Pandu Rangan, P. Nagavamsi, Minimum dominating clique on trapezoidal graphs, manuscript.; C. Pandu Rangan, P. Nagavamsi, Minimum dominating clique on trapezoidal graphs, manuscript. · Zbl 1078.05526
[12] A. Srinivasan, M.S. Chang, K. Madhukar, C. Pandu Rangan, Efficient algorithms for the weighted domination problems on trapezoid graphs, manuscript, 1994; A. Srinivasan, M.S. Chang, K. Madhukar, C. Pandu Rangan, Efficient algorithms for the weighted domination problems on trapezoid graphs, manuscript, 1994
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.