论文标题
最佳的一般因素问题和跳跃系统交集
Optimal General Factor Problem and Jump System Intersection
论文作者
论文摘要
在最佳的一般因素问题中，给定图表$ g =（v，e）$和a $ b（v）\ subseteq \ subseteq \ subseteq \ mathbb z $在v $中的每个$ v \ in v $中的每个$ v \，我们寻求$ $ d_f（v）in $ v $ in $ v $ in $ d $ d $ d $ d_ $ d d DEN的边缘子集$ f $ f $ f $ d n $ d d $ d_至$ v $。 Dudycz和Paluch最近的一项关键工作表明，如果每个$ b（v）$的长度不超过一个，则可以在多项式时间内解决此问题。尽管它们的算法非常简单，但其正确性证明非常复杂。在本文中，我们将最佳的一般因素问题作为跳跃系统交集，并揭示Dudycz和Paluch的算法何时可以应用于该问题的这种抽象形式。通过使用此抽象，我们给出了算法的另一个正确性证明，这比原始算法简单。我们还将结果扩展到有价值的情况。
In the optimal general factor problem, given a graph $G=(V, E)$ and a set $B(v) \subseteq \mathbb Z$ of integers for each $v \in V$, we seek for an edge subset $F$ of maximum cardinality subject to $d_F(v) \in B(v)$ for $v \in V$, where $d_F(v)$ denotes the number of edges in $F$ incident to $v$. A recent crucial work by Dudycz and Paluch shows that this problem can be solved in polynomial time if each $B(v)$ has no gap of length more than one. While their algorithm is very simple, its correctness proof is quite complicated. In this paper, we formulate the optimal general factor problem as the jump system intersection, and reveal when the algorithm by Dudycz and Paluch can be applied to this abstract form of the problem. By using this abstraction, we give another correctness proof of the algorithm, which is simpler than the original one. We also extend our result to the valuated case.
