0
$\begingroup$

Given a graph with $V$ vertices and $k$, find a set $K$ of $k$ vertices of $G$. Let $c(v)$ be the distance (in BFS-like) of the vertex $v \in V$ to the closest vertex $u \in K$. How to choose the set $K$ such that the maximum $c(v) \forall v \in V$ is minimized?

This is like a dominating set, but each vertex covers a range of vertices, and we are interested in minimizing this range.

Improve this question
$\endgroup$
6
  • $\begingroup$ 1. In the first sentence, you say that $K$ is given, but in the third sentence you say you want to choose it. Which is it? I suspect the inputs are the graph and $k$, and the desired output is $K$. I encourage you to edit the question to clarify. 2. Given that you mention the connection to dominating set, I presume you already know that this problem is NP-hard. What kinds of answers are you looking for? Practical algorithms? (If so, can you give us any idea how large $k$ and $|V|$ typically are?) Approximation algorithms? Exponential-time exact algorithms? $\endgroup$
    – D.W. ♦
    May 17 at 19:17
  • $\begingroup$ 1. You are correct, I want to find K. 2. Anything $\endgroup$
    – Powereleven
    May 17 at 20:09
  • $\begingroup$ Have you searched for “minimum k-dominating set problem"? Have you read, for example, Solving the k‑dominating set problem on very large‑scale networks? $\endgroup$
    – John L.
    May 18 at 13:16
  • $\begingroup$ I'll take a look. Ty for the ref $\endgroup$
    – Powereleven
    May 18 at 15:21
  • $\begingroup$ @JohnL. By the way, if I want to find the biggest k-dominating set of cardinality $\leq k$ such that no 2 vertices in K are closer than $d$, do you have a reference? $\endgroup$
    – Powereleven
    May 18 at 15:40

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.