Distance domination and amplifier placement problems

We consider an optimisation problem defined on an undirected graph with a given root vertex and an attenuation parameter s, in which we seek a spanning tree with the smallest number of special (amplifying) vertices such that each vertex in the tree is preceded on its unique path from the root vertex by an amplifying vertex no more than s edges distant. This problem, which we call amplified spanning tree (AST), is motivated by local-access television cable networks. We show that even for planar graphs with no vertex degree exceeding four, for any s>0 the AST problem is NP-complete. Using connections to so-called distance-domination problems, we show that two related problems, including total distance-domination, are also NP-complete, and we derive an approximability upper bound for AST.

Last modified: Tue Jan 23 15:29:26 EST 2007