Consider a directed Steiner tree problem with a source node $s$ a set $T$ of terminals with the following constraint. For each node $v$ on the tree, we assign a branching value $b_v$ as follows. (1) $b(s)=1$; (2) consider vertex $v$ with $m$ children $\{u_i\}_{i=1}^m$, $b_{u_i}=\frac{2m+1}{3m}$. My problem is to find the Steiner tree subject to the constraint that the branching value of each terminal $v\in T$ is lower-bounded by certain threshold, i.e., $b_v\ge \theta_v$.
5
- $\begingroup$ @MaxAlekseyev Thanks for your comments. I edited the problem, which I hope should be more clear now. $\endgroup$lchen– lchen2024-06-14 03:23:17 +00:00Commented Jun 14, 2024 at 3:23
- $\begingroup$ $b_v$ is decreasing function of $m$, and so a lower bound for $b_v$ translates into an upper bound for $m$. It'd be stratforward to state such bounds directly, without even defining $b_v$. $\endgroup$Max Alekseyev– Max Alekseyev2024-06-14 11:18:26 +00:00Commented Jun 14, 2024 at 11:18
- $\begingroup$ I do not quite understand your comment. I am looking for an algorithm constructing the steiner tree. $\endgroup$lchen– lchen2024-06-14 12:19:49 +00:00Commented Jun 14, 2024 at 12:19
- $\begingroup$ My point is that you state quite obscure condition, which in fact translates to just an upper bound for the number of siblings for each terminal node. $\endgroup$Max Alekseyev– Max Alekseyev2024-06-14 14:27:56 +00:00Commented Jun 14, 2024 at 14:27
- $\begingroup$ What do you mean by upper-bound? In fact, the technical difficulty in the problem is that we need to decide whether to branch and how many children, i.e., how to build the tree such that $b_i$ for each leaf is sufficiently high. $\endgroup$lchen– lchen2024-06-20 02:57:34 +00:00Commented Jun 20, 2024 at 2:57
Add a comment |