Minimum 2-tuple dominating set of permutation graphs
详细信息 查看全文
- 作者：Sambhu Charan Barman ; Sukumar Mondal…
- 关键词：Design of algorithms ; Analysis of algorithms ; Domination ; k ; Tuple domination ; 2 ; Tuple domination ; Permutation graphs ; 05C78
- 刊名：Journal of Applied Mathematics and Computing
- 出版年：2013
- 出版时间：October 2013
- 年：2013
- 卷：43
- 期：1-2
- 页码：133-150
- 全文大小：710KB
- 参考文献：1. Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti Spaccamela, A., Protasi, M.: Complexity and Approximation. Springer, Berlin (1999) class="external" href="http://dx.doi.org/10.1007/978-3-642-58412-1">CrossRef
2. Awerbuch, B., Peleg, D.: Sparse partitions (extended abstract). In: 31st Annual Symposium on Foundations of Computer Science, pp. 503-13 (1990) class="external" href="http://dx.doi.org/10.1109/FSCS.1990.89571">CrossRef
3. Benson, D.A., Boguski, M.S., Lipman, D.J., Ostell, J., Ouellette, B.F., Rapp, B.A., Wheeler, D.L.: Nucleic acids research. GenBank
4. Berchtold, S., Keim, D., Kriegel, H.-P.: Transitive orientation of graphs and identification of permutation graphs. In: Proceedings of the 22nd Conference on Very Large Databases, pp. 28-9 (1996)
5. Berchtold, S., Bohm, C., Kriegel, H.P.: The pyramid-technique: towards breaking the curse of dimensionality. In: Proceedings of the SIGMOD Conference, pp. 142-53 (1998)
6. Berger, E.: Dynamic monopolies of constant size. Technical report, Los Alamos National Laboratories (1999)
7. Chang, G.J.: Algorithmic aspect of domination in graphs. In: Du, D.-Z., Paradolas, P.M. (eds.) Handbook of Combinatorial Optimization, vol.?3, pp. 339-05 (1998)
8. Chao, H.S., Hsu, F.R., Lee, R.C.T.: An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs. Discrete Appl. Math.
9. Cockayne, E., Dawes, R., Hedetniemi, S.: Total domination in graphs. Networks
10. De Jaenisch, C.F.: Trait des Applications de l’Analyse Mathematique au Jeu des Echecs. Petrograd (1862)
11. Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)
12. Harary, F., Haynes, T.W.: Double domination in graphs. Ars Comb.
13. Haynes, T.W., Slater, P.J.: Paired-domination in graphs. Networks
14. Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Domination in Graphs: Advanced Topics. Dekker, New York (1998)
15. Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Domination in Graphs: Selected Topics. Dekker, New York (1998)
16. Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Domination in Graphs: The Theory. Dekker, New York (1998)
17. Haynes, T.W., Mynhardt, C.M., van der Merwe, L.C.: Criticality index of total domination. Congr. Numer.
18. Haynes, T.W., Mynhardt, C.M., van der Merwe, L.C.: Total domination edge critical graphs. Util. Math.
19. Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Dekker, New York (1998)
20. Haynes, T.W., Mynhardt, C.M., van der Merwe, L.C.: Total domination edge critical graphs with maximum diameter. Discuss. Math., Graph Theory
21. Liao, C.S., Chang, G.J.: Algorithmic aspect of / k-tuple domination in graphs. Taiwan. J. Math.
22. Liao, C.S., Chang, G.J.: / k-Tuple domination in graphs. Inf. Process. Lett.
23. Lu, C.L., Ko, M.-T., Tang, C.Y.: Perfect edge domination and efficient edge domination in graphs. Discrete Appl. Math.
24. Muller, J.H., Spinrad, J.: Incremental modular decomposition. J. ACM
25. Pnueli, A., Lempel, A., Even, S.: Transitive orientation of graphs and identification of permutation graphs. Can. J. Math.
26. Pramanik, T., Mondal, S., Pal, M.: Minimum 2-tuple dominating set of an interval graphs. Int. J. Comb.
27. Qiao, H., Kang, L., Gardei, M., Du, D.-Z.: Paired-domination of trees. J. Glob. Optim.
28. Shan, E., Dong, Y.: The / k-tuple twin domination in generalized de Bruijn and Kautz networks. Comput. Math. Appl.
29. Sumner, D.P., Blitch, P.: Domination critical graphs. J. Comb. Theory, Ser. B
30. Yannakakis, M., Gavril, F.: Edge domination sets in graphs. SIAM J. Appl. Math. B - 作者单位：Sambhu Charan Barman (1)
Sukumar Mondal (2)
Madhumangal Pal (1)
1. Department of Applied Mathematics with Oceanology and Computer Programming, Vidyasagar University, Midnapore, 721 102, India
2. Department of Mathematics, Raja N.L. Khan Women’s College, Gope Palace, Midnapore, 721 102, India - ISSN：1865-2085
文摘
For a fixed positive integer k, a k-tuple dominating set of a graph G=(V,E) is a subset D⊿em class="a-plus-plus">V such that every vertex in V is dominated by at least k vertex in D. The k-tuple domination number γ ×k (G) is the minimum size of a k-tuple dominating set of G. The special case when k=1 is the usual domination. The case when k=2 was called double domination or 2-tuple domination. A 2-tuple dominating set D 2 is said to be minimal if there does not exist any D′?D 2 such that D-is a 2-tuple dominating set of G. A 2-tuple dominating set D 2, denoted by γ ×2(G), is said to be minimum, if it is minimal as well as it gives 2-tuple domination number. In this paper, we present an efficient algorithm to find a minimum 2-tuple dominating set on permutation graphs with n vertices which runs in O(n 2) time.