Algorithms for multicast connection under multi-path routing model.

DOI10.1016/S0020-0190(02)00220-XMaRDI QIDQ1853101zbMATH OpenOpenAlexFDO

Authors J. Gu, Xiaodong Hu, Mu-Hong Zhang

Publication date 21 January 2003

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(02)00220-x

zbMATH Keywords

Approximation algorithmsMulticast connectionNetwork costRouting algorithms

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Nonnumerical algorithms (68W05)

Review text

Given a source node and a set of destination nodes in a network, multicast routing problem is usually treated as Steiner tree problem. Unlike this well-known tree based routing model, multicast routing under multi-path model is to find a set of paths rooted at the source node such that in each path at most a fixed number of destination nodes can be designated to receive the data and every destination node must be designated in a path to receive the data. The cost of routing is the total costs of paths found. In this paper we study how to construct a multicast routing of minimal cost under multi-path model. We propose two approximation algorithms for this NP-complete problem with guaranteed performance ratios.

Recommendations

• Routing algorithm for multicast under multi-tree model in optical networks
• scientific article; zbMATH DE number 2202244

Cites work

• A fast algorithm for Steiner trees
• A Greedy Heuristic for the Set-Covering Problem
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• Routing to Multiple Destinations in Computer Networks

Cited in

(10)

• A 3.4713-approximation algorithm for the capacitated multicast tree routing problem
• 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
• Anycasting in connection-oriented computer networks: Models, algorithms and results
• scientific article; zbMATH DE number 2088470 (Why is no real title available?)
• scientific article; zbMATH DE number 1981018 (Why is no real title available?)
• scientific article; zbMATH DE number 2202244 (Why is no real title available?)
• An Improved Approximation Algorithm for the Capacitated Multicast Tree Routing Problem
• Bandwidth maximization in multicasting

This page was built for publication: Algorithms for multicast connection under multi-path routing model.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853101)