论文标题
火焰中的贪婪
Greedoids from flames
论文作者
论文摘要
如果对于每一个$ {v \ in v（d）-r} $，则具有$ r \ in v（d）$中的$ r \ in v（d）$中的digraph $ d $是$ r $ - flame，则$ v $的内度等于本地edge-connectivity $λ_d（r，v）$。我们表明，对于v（d）$中的每一个digraph $ d $和$ r \ \ r \ \ r \ \ r \，$ r $ flame子图的边缘集合$ d $的greedoid形成了贪婪。我们的方法得出了lovász'therem的新证明：对于每一个digraph $ d $和$ r \ in v（d）$中，有一个$ r $ -flame subdigraph $ f $ $ d $的$ d $，因此$λ_f（r，v）=λ_d（r，v）$ vis_d（r，v）$ for $ v \ in V in v in v in v in v in v in v in（d） - $ $。我们还提供了一种强烈的多项式算法，以找到与lovász'therem的分数概括一起使用的$ f $。
A digraph $ D $ with $ r\in V(D) $ is an $ r $-flame if for every $ {v\in V(D)-r} $, the in-degree of $ v $ is equal to the local edge-connectivity $ λ_D(r,v) $. We show that for every digraph $ D $ and $ r\in V(D) $, the edge sets of the $ r $-flame subgraphs of $ D $ form a greedoid. Our method yields a new proof of Lovász' theorem stating: for every digraph $ D $ and $ r\in V(D) $, there is an $ r $-flame subdigraph $ F $ of $ D $ such that $ λ_F(r,v) =λ_D(r,v) $ for $ v\in V(D)-r $. We also give a strongly polynomial algorithm to find such an $ F $ working with a fractional generalization of Lovász' theorem.
