Given a graph G = (V,E) with edge and vertex weights. The minimum distance r-dominating set problem for a graph G = (V,E) requires to find a set S $\in$ V of smallest vertex-weight such that every vertex v not in S, there is a vertex u in S such that d(u,v) $\leq$ r. Distance is defined by the length of shortest path on graph. Does anyone know papers that solve this problem on a $\textbf{tree}$?
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ This looks like a standard (if somewhat advanced) dynamic programming problem, at least if all the edge-weights are non-negative. $\endgroup$– JeffεCommented Jan 26, 2014 at 4:18
-
$\begingroup$ Yes! JeffE. This problem could be solved by using dynamic programming. It takes O(r^2.|V|) with memory O(r). But I just want to check whether my algorithm is optimal or not. I found a paper that do better than my algorithm, O(1) memory with the same running time, but for trees with only edge weights. $\endgroup$– Hung LeCommented Jan 26, 2014 at 5:37
-
$\begingroup$ O(r) and O(1) I mean for each node of the tree. $\endgroup$– Hung LeCommented Jan 26, 2014 at 5:46
-
2$\begingroup$ @Hunglv you should include such knowledge and the more precise "I am looking for lower bounds" as part of your question, so that we can better answer it and don't accidentally close it. $\endgroup$– Artem Kaznatcheev ♦Commented Jan 26, 2014 at 16:08
-
$\begingroup$ There's probably a four-russians optimization that improves the running time by some polyloglog factor. (At a high level: Precompute the answer to all subproblems of size $O(\log\log n)$, and then use the results of that precomputation as base cases in the dynamic programming algorithm.) If you're really looking for a proof that no polynomial improvement is possible, the correct answer is almost certainly "nobody knows". We really have no idea how to prove superlinear lower bounds for anything. $\endgroup$– JeffεCommented Jan 26, 2014 at 20:19
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The problem is solved in the paper P. Slater. R-domination in graphs. J. ACM, 23(3):446–450, July 1976. It considers an even more general problem using dynamic programming.
