Design and Analysis of Algorithms for (T,R) Broadcast Domination Problems(2/2)

Project Details


Due to a practical resource sharing problem, Blessing, Johnson, Mauretour, and Inskoconsider a variation of the domination problem which they call the (t,r) broadcast dominationproblem recently. They collect a vertex subset D that every vertex v in D can get a completeresource, using t to weight. Moreover, the vertex v in D can offer partial resource, using t-i toweight, to the vertex u with d(u,v)=i < t, and offer no resource, using 0 to weight, to othersvertices which have the distance at least t with v. For each vertex in the graph, the totalweight 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 upperbounds for large grid graphs with t≦3. Actually, I can prove this problem is NP-complete onbipartite graph. Moreover, it is known that the problem is polynomial time if every vertex ofD can broadcast different weight which means that there is a function f from vertex set tononnegative 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 efficientalgorithms for (t,r) broadcast domination problems on some regular graphs. To complete theprevious work, I will also study the related L(p,q)-labeling problems inedge-path-replacement graphs.
Effective start/end date1/08/1831/07/19


Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.