| 摘要: | 原本的圖形上的控制問題是找最少數目的點集合,使得圖上的任一點若不在這個 點集合裡,那與它相連接的點裡,至少有一點是落在這個點集合裡.由於實際上的資源分 享問題而考慮(t,r)擴散控制,1≦r≦t,希望找最少數目的點集合,集合裡的每個點給予 完整的資源(用t 來衡量),這集合裡的點會供給與它距離為i 的點部分資源(用t-i 來衡 量),所以與它最短距離≧t 的點就得不到它的資源,而圖上任一點都必須得到一定份量 的資源供給(至少是r), 而目前僅有m x n 格子圖在t≦3, m≦5 有些確切值, 一般的 格子圖也只t≦3 有上界.我已經能證明這樣的問題就算只考慮二部圖也是NP-complete. 若是不限定集合的點給予資源皆相同, 只要求集合裡的所有點其資源總量要最少,則已 知是polynomial time 就可解決的問題,一些特定的圖上還可以找到linear time 的演 算法.所以希望再加入t 的限制後,一些規律的圖上能找到有效率的演算法來處理這樣 的資源分配問題. 另外延續之前的工作, 繼續對有關的圖形標號相關問題加以研究. ;Due to a practical resource sharing problem, Blessing, Johnson, Mauretour, and Insko consider a variation of the domination problem which they call the (t,r) broadcast domination problem recently. They collect a vertex subset D that every vertex v in D can get a complete resource, using t to weight. Moreover, the vertex v in D can offer partial resource, using t-i to weight, to the vertex u with d(u,v)=i < t, and offer no resource, using 0 to weight, to others vertices which have the distance at least t with v. For each vertex in the graph, the total weight of the vertex must be at least r with 1≦r≦t. They determine the exact values of (t,r) broadcast domination number only for small grid graphs with t≦3. They also give upper bounds for large grid graphs with t≦3. Actually, I can prove this problem is NP-complete on bipartite graph. Moreover, it is known that the problem is polynomial time if every vertex of D can broadcast different weight which means that there is a function f from vertex set to nonnegative integers such that every vertex u can broadcast f(u)-d(u,v) to vertex v if d(u,v) ≦ f(u) and each vertex must receive at least r. In this project, I want to design efficient algorithms for (t,r) broadcast domination problems on some regular graphs. To complete the previous work, I will also study the related L(p,q)-labeling problems in edge-path-replacement graphs. |
