臺灣博碩士論文加值系統

所謂圖形上的廣播支配是找出一個函數讓此圖形上的每個點都對應到一個大於等於零的整數使得這個函數滿足對於圖形上的每個點，至少都有一個值大於零的點跟它的距離是在這個值之間。而圖形上的廣播支配問題則是在該圖形上找出一個符合廣播支配的函數，使得每個點所對應的值加起來之總和是最小的。在這篇論文中，我們針對廣播支配問題做一個綜述以及提出一些和半徑樹(廣播支配函數對應值的總和為半徑長的樹)有關的特徵描述。

A broadcast domination function on a graph $G=(V,E)$ is a function $f$ that maps $V$ into $\{0,1,\dots,k\}$ such that every vertex of $G$ within distance $f(v)$ from some vertex $v$ with $f(v)>0$. The cost of a broadcast domination function $f$ is $\Sigma_{v\in V}f(v)$. The broadcast domination problem on $G$ is to find a minimum cost broadcast domination function on $G$.
In this thesis, we present an overview of the broadcast domination problem and some results on characterizations of radial trees.

Abstract i
Acknowledgement ii
Contents iii
List of Figures iv
1 Introduction 1
2 Preliminaries 3
3 An overview of previous results 6
3.1 General graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 Interval graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3 Series-parallel graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.4 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4 Some characterizations of radial trees 28
5 Conclusion 35
Bibliography 36

[1] D.W. Bange, A.E. Barkauskas, and P.J. Slater, Efficient dominating sets in
graphs, In R.D. Ringeisen and F.S. Roberts, editors, Applications of Discrete
Mathematics, pp. 189–199, SIAM, Philadelphia, PA, 1988.
[2] J.R.S. Blair, P. Heggernes, S. Horton, and F. Manne, Broadcast domination
algorithms for interval graphs, series-parallel graphs, and trees, Congr. Numer.
169 (2004), pp. 55–77.
[3] K.S. Booth, J.H. Johnson, Dominating sets in chordal graphs, SIAM J. Com-
puting 11 (1982), pp. 191–199.
[4] A. Brandst‥adt, V.D. Chepoi, F.F. Dragan, The algorithmic use of hypertree
structure and maximum neighbourhood orderings, Discrete Applied Mathmetics
82 (1998), pp. 43–77.
[5] A. Brandst‥adt, V.B. Le, and J.P. Spinrad, Graph classes: A survey, SIAM Monographs
on Discrete Mathematics and Applications, Philadelphia, 1999.
[6] G.J. Chang and G.L. Nemhauser, The k-domination and k-stability problem on
graphs, Technical Report 540, School of Operations Res. and Industrial Eng.,
Cornell Univ, 1982.
[7] M.-S. Chang, Efficient algorithms for the domination problems on interval and
circular-arc graphs, SIAM J. Computing 27 (1998), pp. 1671–1694.
[8] J. Dabney, B.C. Dean, and S.T. Hedetniemi A linear-time algorithm for broadcast
domination in a tree, to appear in Networks.
[9] X. Deng, P. Hell, and J. Huang, Linear time representation algorithms for proper
circular arc graphs and proper interval graphs, SIAM J. Computing 25 (1996),
pp. 390–403.
[10] A.K. Dewdeny, Fast Turing reductions between problems in NP, Technical Report
71, Dept. of Computer Science, University of West Ontario, 1981.
[11] J.E. Dunbar, D.J. Erwin, T.W. Haynew, S.M. Hedetniemi, and S.T. Hedetniemi,
Broadcasts in graphs, Discrete Applied Mathmetics 154 (2006), pp. 59–75.
[12] D.J. Erwin, Dominating broadcasts in graphs, Bull. Inst. Comb. Appl. 42 (2004),
pp. 89–105.
[13] M. Farber, Domination, independent domination, and duality in strongly chordal
graphs, Discrete Applied Mathmetics 7 (1984), pp. 115–130.
[14] M.R. Fellows and M.N. Hoover, Perfect domination, Australas, J. Combin. 3
(1991), pp. 141–150.
[15] C. de Figueiredo, J. Meidanis, and C.P. de Mello, A linear time algorithm for
proper interval graph recognition, Information Processing Letters 56 (1995), pp.
179–184.
[16] M.R. Grary and D.S. Johnson, Computers and Intractability: A Guide to the
Theory of NP-Completeness, W. H. Freeman and Co., New York, NY, 1979.
[17] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in
Graphs, Marcel Dekker, Inc., New-York, 1998.
[18] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater (Eds.), Domination in graphs:
Advanced Topics, Marcel Dekker, Inc., New-York, 1998.
[19] P. Heggernes and D. Lokshtanov, Optimal broadcast dominaton in polynomial
time, Discrete Mathmetics 306 (2006), pp. 3267–3280.
[20] W.-L. Hsu and K.-H. Tsai, Linear time algorithms on circular-arc graphs, Infor-
mation Processing Letters 40 (1991), pp. 123–129.
[21] D. Kratsch, Domination and total domination in asteroidal triple-free graphs,
Discrete Applied Mathmetics 99 (2000), pp. 111–123.
[22] C.L. Liu, Introduction to Combinatorial Mathematics, McGraw-Hill, New York,
NY, 1968.
[23] G. Ramalingan and C.P. Rangan, A unified approach to domination problems
on interval graphs, Information Processing Letters 27 (1988), pp. 271–274.
[24] P.J. Slater, R-Domination in Graphs, J. Assoc. Comput. Mach. 23 (1976), pp.
446–450.
[25] C.B. Smart and P.J. Slater, Complexity results for closed neighborhood order
parameters, Congr. Numer. 112 (1995), pp.83–96.
[26] J. Valdes, R.E. Tarjan, and E.L. Lawler, The recognition of series parallel digraphs,
SIAM J. Computing 11 (1982), pp. 298–313.
[27] D.B. West, Introduction to Graph Theory, Second Edition, Prentice Hall 2001.