3
$\begingroup$

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}$?

$\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ε
    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 Le
    Jan 26, 2014 at 5:37
  • $\begingroup$ O(r) and O(1) I mean for each node of the tree. $\endgroup$
    – Hung Le
    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$ 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ε
    Jan 26, 2014 at 20:19

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.