設計與探討圖形上有(t,r)關擴散控制的演算法;Design and Analysis of Algorithms for (T,R) Broadcast Domination Problems

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/78808

Title:	設計與探討圖形上有(t,r)關擴散控制的演算法;Design and Analysis of Algorithms for (T,R) Broadcast Domination Problems
Authors:	廖勝強
Contributors:	國立中央大學數學系
Date:	2018-12-19
Issue Date:	2018-12-20 13:51:08 (UTC+8)
Publisher:	科技部
Abstract:	原本的圖形上的控制問題是找最少數目的點集合,使得圖上的任一點若不在這個點集合裡,那與它相連接的點裡,至少有一點是落在這個點集合裡.由於實際上的資源分享問題而考慮(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.
Relation:	財團法人國家實驗研究院科技政策研究與資訊中心
Appears in Collections:	[Department of Mathematics] Research Project

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	231	View/Open

社群 sharing

Loading...