Loading...
Please wait, while we are loading the content...
Similar Documents
Scheduling multicasts on unit-capacity trees and meshes (1998).
| Content Provider | CiteSeerX |
|---|---|
| Author | Henzinger, Monika Rauch Leonardi, Stefano |
| Abstract | This paper studies the multicast routing and admission control problem on unit-capacity tree and mesh topologies in the throughput-model. The problem is a generalization of the edge-disjoint paths problem and is NP-hard both on trees and meshes. We study both the offline and the online version of the problem: In the offline setting, we give the first constant-factor approximation algorithm for trees, and an O((log log n)²)-factor approximation algorithm for meshes. In the online setting, we give the first polylogarithmic competitive online algorithm for tree and mesh topologies. No polylogarithmic-competitive algorithm is possible on general network topologies [8] and there exists a polylogarithmic lower bound on the competitive ratio of any online algorithm on tree topologies [3]. We prove the same lower bound for meshes. |
| File Format | |
| Publisher Date | 1998-01-01 |
| Access Restriction | Open |
| Subject Keyword | Unit-capacity Tree Mesh Topology Log Log General Network Topology Competitive Ratio Edge-disjoint Path Problem Polylogarithmic-competitive Algorithm Online Version First Polylogarithmic Competitive Online Algorithm Tree Topology Offline Setting Admission Control Problem First Constant-factor Approximation Algorithm Online Algorithm Online Setting Factor Approximation Algorithm Paper Study Multicast Routing |
| Content Type | Text |
| Resource Type | Article |
