|
The problem of computing a minimum cost subgraph D'=(V,A') of a directed graph D=(V,A) so that D' contains k edge-disjoint paths from a specified root r \in V to every other node in V is known to be nicely solvable since it can be formulated as a matroid intersection problem. A corresponding problem when openly disjoint paths are requested rather than edge-disjoint was solved in [12] with the help of submodular flows. Here we show that the use of submodular flows is actually avoidable and even a common generalization of the two rooted k-connection problems is a matroid intersection problem. We also provide a polyhedral description using supermodular functions on bi-sets and this approach enables us to handle more general rooted k-connection problems. For example, with the help of a submodular flow algorithm the following restricted version of the generalized Steiner-network problem is solvable in polynomial time: given a digraph D=(V,A) with a root-node r, a terminal set T, and a cost function c:A \to R+ so that each edge of positive cost has its head in T, find a subgraph D'=(V,A') of D of minimum cost so that there are k openly disjoint paths in D' from r to every node in T.
Bibtex entry:
| AUTHOR | = | {Frank, Andr{\'a}s}, |
| TITLE | = | {Rooted k-connections in digraphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2006}, |
| NUMBER | = | {TR-2006-07} |