A 3.4713-approximation algorithm for the capacitated multicast tree routing problem

DOI10.1016/j.tcs.2009.05.013zbMath1192.68873OpenAlexW2091897018MaRDI QIDQ1040584

Zhipeng Cai, Zhi-Zhong Chen, Guo-Hui Lin

Publication date: 25 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.05.013

zbMATH Keywords

approximation algorithmSteiner minimum treetree partitioningcapacitated multicast tree routing

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Approximation algorithms (68W25)

Related Items

OFDP: a distributed algorithm for finding disjoint paths with minimum total length in wireless sensor networks, Metric and Distributed On-Line Algorithm for Minimizing Routing Interference in Wireless Sensor Networks, \((\alpha,\tau )\)-monitoring for event detection in wireless sensor networks, Approximate event detection over multi-modal sensing data, Efficient accuracy evaluation for multi-modal sensed data, Approximate Aggregation for Tracking Quantiles in Wireless Sensor Networks, Size-constrained tree partitioning: approximating the multicast \(k\)-tree routing problem, Balanced tree partition problems with virtual nodes, DOAMI: a distributed on-line algorithm to minimize interference for routing in wireless sensor networks, On multi-path routing for reliable communications in failure interdependent complex networks

Cites Work

• Unnamed Item
• Algorithms for multicast connection under multi-path routing model.
• Routing algorithm for multicast under multi-tree model in optical networks
• An improved approximation algorithm for capacitated multicast routings in networks
• An improved approximation algorithm for multicast \(k\)-tree routing
• Routing to Multiple Destinations in Computer Networks
• Automata, Languages and Programming
• An Improved Approximation Algorithm for the Capacitated Multicast Tree Routing Problem
• Computing and Combinatorics