摘要(英) |
Due to a practical resource sharing problem, we consider a variation of the domination problem in this thesis which we call the distance-two domination problem.
This thesis is organized as follows. Section 1 gives basic definitions and notation. Section 2 investigates the distance-two domination of paths and cycles. Section 3 shows that D_{3,2,1}-domination problem is NP-complete for bipartite graphs. And we determine the D_{3,2,1}-domination number of fully binary tree in the final section. |
參考文獻 |
References
[1] A. V. Aho, J. E. Hopcroft and J. D. Ullman, The Desing and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA (1974).
[2] G. J. Chang, Algorithmic Aspects of Domination in Graphs, Handbook of Com-binatorial Optimization (D. Z. Du and P. M. Pardalos edited) Vol. 3 (1998),339-405.
[3] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Domination in Graphs: Ad-vanced Topics, Marcel Dekker, NY (1998).
[4] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, NY (1998).
[5] E. Horowitz and S. Sahni, Fundamentals of Computer Algorithms, Computer Science Press, Rockville, MD (1978).
[6] U. Manber, Introduction to Algorithms, Addison-Wesley, Reading, MA (1989).
[7] D. B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, NJ (2001). |