1
$\begingroup$

A spider is a tree with at most one vertex of degree greater than 2. This vertex is called the head of the spider.

I am interested in the following problem: We are given an undirected graph $G = (V,E)$ with a specified vertex $h \in V$ (the head), and a set of terminals $R \subseteq V$. Also, each edge has a non-negative cost $c_e$.

The goal is to compute a minimum-cost spider with head $h$ and leaves $R$.

This problem is a special case of degree-bounded Steiner Tree, where each vertex has an upper bound on its allowed degree. But I was wondering if there is a simpler result in this case?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Did you try solving it via min-cost flow? You want internally node-disjoint paths from the terminals to $h$ of minimum cost. $\endgroup$
    – Chandra Chekuri
    Jul 12, 2022 at 11:47
  • $\begingroup$ @ChandraChekuri yeah, that seems to work. Thanks! $\endgroup$
    – Karagounis Z
    Jul 13, 2022 at 22:54

0

Reset to default

Your Answer

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