A Greedy Multicast Algorithm in ★-Ary n-Cubes and Its Worst Case Analysis (<Special Issue>Special Issue on Selected Papers from LA Symposium)
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, we consider the problem of multicasting a message in k-ary n-cubes under the store-and-forward model. The objective of the problem is to minimize the size of the resultant multicast tree by keeping the distance to each destination over the tree the same as the distance in the original graph. In the following, we first propose an algorithm that grows a multicast tree in a greedy manner, in the sense that for each intermediate vertex of the tree, the outgoing edges of the vertex are selected in a non-increasing order of the number of destinations that can use the edge in a shortest path to the destination. We then evaluate the goodness of the algorithm in terms of the worst case ratio of the size of the generated tree to the size of an optimal tree. It is proved that for any k★5 and n★6, the performnance ratio of the greedy algorithm is c★kn-★(n) for some constant 1/12★c★1/2.
- 2003-02-01
著者
関連論文
- A Fault-Tolerant Content Addressable Network(Networks)
- A Localization Scheme for Sensor Networks Based on Wireless Communication with Anchor Groups(Challenges in Ad-hoc and Multi-hop Wireless Communications)
- CHQ : A Multi-Agent Reinforcement Learning Scheme for Partially Observable Markov Decision Processes(Artificial Intelligence and Cognitive Science)
- On Some Computational Aspect of Point Configurations in the Enclidean Space
- An Efficient Scheduling Scheme for Assigning Transmission Opportunity in QoS-Guaranteed Wireless LAN
- A Generic Solver Based on Functional Parallelism for Solving Combinatorial Optimization Problems(Distributed Cooperation and Agents)
- SwRED: a robust active queue management scheme based on load level prediction (情報ネットワーク)
- A New Caching Technique to Support Conjunctive Queries in P2P DHT
- Semi-Dynamic Multiprocessor Scheduling with an Asymptotically Optimal Performance Ratio
- A Greedy Multicast Algorithm in ★-Ary n-Cubes and Its Worst Case Analysis (Special Issue on Selected Papers from LA Symposium)
- Importance of intracellular Fe pools on growth of marine diatoms by using unialgal cultures and on the Oyashio region phytoplankton community during spring
- Autonomous Multi-Source Multi-Sink Routing in Wireless Sensor Networks
- Autonomous Multi-Source Multi-Sink Routing in Wireless Sensor Networks
- Special Section on Discrete Mathematics and Its Applications
- Reputation-Based Colluder Detection Schemes for Peer-to-Peer Content Delivery Networks