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 and acknowledge that you have read and understand our privacy policy and code of conduct.