论文标题
在指定稳定集中的最小跨越树木的顶点界限
Minimum Spanning Trees with Bounded Degrees of Vertices in a Specified Stable Set
论文作者
论文摘要
给定一个图$ g $，并设置$ \ {α_v〜 | 〜v \ in V（g）\} $和$ \ {β_V〜 | 〜v \ in V（g）\} $的非阴性整数的$ \ in V（g）$是$ np $ -complete。在本文中，我们通过要求仅适用于u $的顶点$ v \的学位限制来放松问题，其中$ u $是$ g $的稳定集。在这种情况下，问题变得可以解决。 答：弗兰克（Frank）提出了一个结果，以表征那个放松问题的积极实例。使用J. Edmonds开发的Matroid交叉点，我们给出了弗兰克的结果的新证明，并表明，如果$ u $稳定并且$ g $的边缘由任意实数加权，那么即使是$α_v\ le d_t（v）\ leβ_v$ for un $ v \ in un a的最低成本$ t $，即
Given a graph $G$ and sets $\{α_v~|~v \in V(G)\}$ and $\{β_v~|~v \in V(G)\}$ of non-negative integers, it is known that the decision problem whether $G$ contains a spanning tree $T$ such that $α_v \le d_T (v) \le β_v $ for all $v \in V(G)$ is $NP$-complete. In this article, we relax the problem by demanding that the degree restrictions apply to vertices $v\in U$ only, where $U$ is a stable set of $G$. In this case, the problem becomes tractable. A. Frank presented a result characterizing the positive instances of that relaxed problem. Using matroid intersection developed by J. Edmonds, we give a new and short proof of Frank's result and show that if $U$ is stable and the edges of $G$ are weighted by arbitrary real numbers, then even a minimum-cost tree $T$ with $α_v \le d_T (v) \le β_v $ for all $v \in U$ can be found in polynomial time if such a tree exists.
