Skip to main content
Notice removed Authoritative reference needed by CommunityBot
Bounty Ended with no winning answer by CommunityBot
deleted 3 characters in body
Source Link
lchen
  • 327
  • 4
  • 14

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$ recursively 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$.

Consider a 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$ recursively 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$.

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$.

Notice added Authoritative reference needed by lchen
Bounty Started worth 50 reputation by lchen
Source Link
lchen
  • 327
  • 4
  • 14

A variant of Steiner tree

Consider a 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$ recursively 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$.