



















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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。