论文标题
在挖掘和加权挖掘的dijoins上
On packing dijoins in digraphs and weighted digraphs
论文作者
论文摘要
令$ d =（v，a）$为挖掘物。 A dicut is a cut $δ^+(U)\subseteq A$ for some nonempty proper vertex subset $U$ such that $δ^-(U)=\emptyset$, a dijoin is an arc subset that intersects every dicut at least once, and more generally a $k$-dijoin is an arc subset that intersects every dicut at least $k$ times.我们的第一个结果是，可以将$ a $划分为dijoin和$（τ-1）$ - dijoin，其中$τ$表示DICUT的最小尺寸。伍德尔（Woodall）提出了更强有力的声明，即$ a $可以将其分配到$τ$ dijoins中。 令$ w \ in \ mathbb {z}^a _ {\ geq 0} $，假设每个dicut至少都有$τ$，对于某些整数$τ\ geq 2 $。令$ρ（τ，d，w）：= \ frac {1}τ\ sum_ {v \ in v} m_v $，其中每个$ m_v $都是$ \ {0,1，\ ldots，τ-1 \} $等于$ w（us）的整数。我们证明了以下结果：（i）如果$ρ（τ，d，w）\ in \ {0,1 \} $，则有一个公平的$ w $ W $ WAUTER-WAUMETER-WAUMEWERTIAN-w $ WAUTHED码的大小$τ$的Dijoins。 （ii）如果$ρ（τ，d，w）= 2 $，则有一个$ W $加权的大小$τ$的Dijoins。 （iii）如果$ρ（τ，d，w）= 3 $，$τ= 3 $，而$ w = {\ bf 1} $，则可以将$ a $划分为三个dijoins。 每个结果都是最好的：（i）也不适合$ρ（τ，d，w）= 2 $，即使$ w = \ 1 $，（ii）不能以$ρ（τ，d，d，w）= 3 $而保持，并且（iii）不适合一般$ w $。
Let $D=(V,A)$ be a digraph. A dicut is a cut $δ^+(U)\subseteq A$ for some nonempty proper vertex subset $U$ such that $δ^-(U)=\emptyset$, a dijoin is an arc subset that intersects every dicut at least once, and more generally a $k$-dijoin is an arc subset that intersects every dicut at least $k$ times. Our first result is that $A$ can be partitioned into a dijoin and a $(τ-1)$-dijoin where $τ$ denotes the smallest size of a dicut. Woodall conjectured the stronger statement that $A$ can be partitioned into $τ$ dijoins. Let $w\in \mathbb{Z}^A_{\geq 0}$ and suppose every dicut has weight at least $τ$, for some integer $τ\geq 2$. Let $ρ(τ,D,w):=\frac{1}τ\sum_{v\in V} m_v$, where each $m_v$ is the integer in $\{0,1,\ldots,τ-1\}$ equal to $w(δ^+(v))-w(δ^-(v))$ mod $τ$. We prove the following results: (i) If $ρ(τ,D,w)\in \{0,1\}$, then there is an equitable $w$-weighted packing of dijoins of size $τ$. (ii) If $ρ(τ,D,w)= 2$, then there is a $w$-weighted packing of dijoins of size $τ$. (iii) If $ρ(τ,D,w)=3$, $τ=3$, and $w={\bf 1}$, then $A$ can be partitioned into three dijoins. Each result is best possible: (i) does not hold for $ρ(τ,D,w)=2$ even if $w=\1$, (ii) does not hold for $ρ(τ,D,w)=3$, and (iii) do not hold for general $w$.
