A note on disjoint arborescences |
| |
Authors: | Satoru Fujishige |
| |
Institution: | 1. Research Institute for Mathematical Sciences, Kyoto University, Kyoto, 606-8502, Japan
|
| |
Abstract: | Recently Kamiyama, Katoh, and Takizawa have shown a theorem on packing arc-disjoint arborescences that is a proper extension of Edmonds’ theorem on disjoint spanning branchings. We show a further extension of their theorem, which makes clear an essential rôle of a reachability condition played in the theorem. The right concept required for the further extension is “convexity” instead of “reachability”. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|