Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Minimum
k
Arborescences with
Bandwidth Constraints
| |
|
Minimum k Arborescences with
Bandwidth Constraints
Mao-cheng Cai1  , Xiaotie
Deng2 and Lusheng Wang1
| (1) |
Institute of Systems Science, Academy of
Mathematics and Systems Sciences, Chinese Academy of Sciences, Beijing 100080, People’s Republic of China |
| (2) |
Department of Computer cience, City University of Hong Kong, Kowloon, Hong Kong |
Received: 20 December 2000 Revised: 22 February 2002 Published online: 5 December 2003
Abstract
Let $G =(V,A)$ be a digraph with source $r$. A weight function
$w$ and bandwidth constraint function $b$ (positive integer) on
$A$ are given. We present algorithms for
finding $k$ $r$-arborescences in $G$
with minimum total weight and with bandwidth constraints.
Digraph - Arborescence - Matroid - Polymatroid - Polymatroid
intersection - Maximum flow - Algorithm and
complexity
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|