Approzimating the Generalized Capacitated Tree-Routing Problem
In this paper, we introduce the generalized capacitated tree-routing problem (GCTR), which is described as follows. Given a connected graph G=(V, E) with a sink s ∈ V and a set M C V-s of terminals with a nonnegative demand q(v), v ∈ M, we wish to find a collection T=T1, T2,..., Te of trees rooted at s to send all the demands to s, where the total demand collected by each tree Ti is bounded from above by a demand capacity k > 0.Let λ > 0 denote a bulk capacity of an edge, and each edge e € E has an installation cost w(e)≥0 per bulk capacity; each edge e is allowed to have capacity kX for any integer k, which installation incurs cost kw(e). To establish a tree routing Ti, each edge e contained in Ti requires α + βq amount of capacity for the total demand q that passes through edge e along Ti and prescribed constants α, β≥0, where a means a fixed amount used to separate the inside of the routing Ti from the outside while term βq means the net capacity proportional to q. The objective of GCTR is to find a collection T of trees that minimizes the total installation cost of edges. Then GCTR is a new generalization of the several known multicast problems in networks with edge/demand capacities. In
Ehab Morsy Hiroshi Nagamochi
Department of Applied Mathematics and Physics Graduate School of Informatics, Kyoto University Yoshi Department of Applied Mathematics and Physics Graduate School of Informatics, Kyoto University Yoshi
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
621-630
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）