𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The stochastic weighted complexity of a group covering of a digraph

✍ Scribed by Iwao Sato

Publisher
Elsevier Science
Year
2008
Tongue
English
Weight
138 KB
Volume
429
Category
Article
ISSN
0024-3795

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the Cover Polynomial of a Digraph
On the Cover Polynomial of a Digraph
✍ F.R.K. Chung; R.L. Graham πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 511 KB
A generalization of the weighted set cov
A generalization of the weighted set covering problem
✍ Jian Yang; Joseph Y-T. Leung πŸ“‚ Article πŸ“… 2005 πŸ› John Wiley and Sons 🌐 English βš– 122 KB

## Abstract We study a generalization of the weighted set covering problem where every element needs to be covered multiple times. When no set contains more than two elements, we can solve the problem in polynomial time by solving a corresponding weighted perfect __b__‐matching problem. In general,

Covering a Strong Digraph by Ξ±βˆ’1 Disjoin
Covering a Strong Digraph by Ξ±βˆ’1 Disjoint Paths: A Proof of Las Vergnas' Conjecture
✍ StΓ©phan ThomassΓ© πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 83 KB

The Gallai Milgram theorem states that every directed graph D is spanned by :(D) disjoint directed paths, where :(D) is the size of a largest stable set of D. When :(D)>1 and D is strongly connected, it has been conjectured by Las Vergnas that D is spanned by an arborescence with :(D)&1 leaves. The