Abstract
The weighted efficient domination problem was solved in O(nm) time for cocomparability graphs [6]. This paper investigates whether more efficient algorithms can be found for permutation graphs and trapezoid graphs - subclasses of cocomparability graphs. Specifically, we present an O(n + \(\bar m\)) algorithm for the weighted efficient domination problem on permutation graphs and an O(n log log n + \(\bar m\)) algorithm on trapezoid graphs, where \(\bar m\)denotes the number of edges in the complement of G.
Preview
Unable to display preview. Download preview PDF.
References
Bange, D., Barkauskas, A., Slater, P.J.: Disjoint dominating sets in trees. Sandia Laboratories Report. SAND 78-1087J (1978)
Bange, D., Barkauskas, A., Slater, P.J.: Efficient dominating sets in graphs. in: Ringeisen, R.D. and Roberts, F.S. eds. Application of Discrete Mathematics. (SIAM, Philadelphia, PA, 1988) 189–199
Biggs, N.: Perfect codes in graphs. J. Combin. Theory Ser. B. 15 (1973) 289–296
Biggs, N.: Perfect codes and distance transitive graphs. in: McDonough, F.P. and Mavron, V.C. eds. Combinatorias: Proc. Fourth British Combinatorial Conference. London Mathematical Society Lecture Notes. 13 (1973) 1–8
Chang, M.S., Liu, Y.C.: Polynomial algorithm for the weighted perfect domination problems on chordal graphs and split graphs. Information Processing Letters. 48 (1993) 205–210
Chang, G.J., Rangan, C.P., Coorg, S.R.: Weighted independent perfect domination on cocomparability graphs. Discrete Applied Mathematics. 63 (1995) 215–222
Cheah, F.: A recognition algorithm for II-graph. Technical Report 246/90. University of Toronto. (1990)
Cheah, F., Corneil, D.G.: On the structure of trapezoid graphs. Discrete Applied Mathematics. 66 (1996) 109–133
Dagan, I., Golumbic, M.C., Pinter,R.Y.: Trapezoid graphs and their coloring. Discrete Appl. Math. 21 (1988) 35–46
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. (Academic Press, New York, 1980)
Livingston, M., Stout, Q.F.: Perfect dominating sets. Congr. Numer. 79 (1990) 187–203
Lu, C.L., Tang, C.Y.: The complexity of the efficient edge domination problem. The 12th Workshop on Combinatorial Mathematics and Computation Theory. Kaohsiung. R.O.C. (1995)
Lu, C.L., Tang, C.Y.: Efficient domination on bipartite graphs. (submitted)
Mehlhorn, K.: Data Structures and Algorithms 1: Sorting and Searching. (Springer-Verlag, 1984)
Ma, T.H.: Algorithm on special classes of graphs and partially ordered sets. Ph.D. Thesis. Dept. of Computer Science. Vanderbilt Univ. Nashville. TN (1990)
Ma, T.H., Spinrad, J.: An O(n 2) algorithm for the 2-chain problem on certain classes of perfect graphs. in: Proceedings of the second annual ACM-SIAM symposium on discrete algorithms (1991) 363–372
Ma, T.H., Spinrad, J.: Avoiding matrix multiplication. in: Möhring, R.H. ed. Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science. Vol. 484 (Springer, Berlin, 1991) 61–71
Pnueli,A., Lempel, A., Even, S.: Transitive orientation of graphs and identification of permutation graphs. Canadian J. of Math. 23 (1971) 160–175
Spinrad, J.R.: On comparability and permutation graphs. SIAM J. Comput. 14 (1985) 658–670
Yen, C.C.: Algorithmic aspects of perfect domination, Ph.D. Thesis. Department of Computer Science. National Tsing Hua University. Taiwan. R.O.C. (1992)
Yen, C.C., Lee, R.C.T.: The weighted perfect domination problem and its variants. Discrete Applied Mathematics. 66 (1996) 147–160
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Liang, Y.D., Lu, C.L., Tang, C.Y. (1997). Efficient domination on permutation graphs and trapezoid graphs. In: Jiang, T., Lee, D.T. (eds) Computing and Combinatorics. COCOON 1997. Lecture Notes in Computer Science, vol 1276. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0045090
Download citation
DOI: https://doi.org/10.1007/BFb0045090
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63357-0
Online ISBN: 978-3-540-69522-6
eBook Packages: Springer Book Archive