Scheduling multicasts on unit-capacity trees and meshes Henzinger, Monika H ; https://orcid.org/0000-0002-5008-6530 Leonardi, Stefano 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 -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 (Lower bounds for on-line graph problems with application to on-line circuits and optical routing, in: Proceedings of the 28th ACM Symposium on Theory of Computing, 1996, pp. 531–540) and there exists a polylogarithmic lower bound on the competitive ratio of any online algorithm on tree topologies (Making commitments in the face of uncertainity: how to pick a winner almost every time, in: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 1996, pp. 519–530). We prove the same lower bound for meshes. Elsevier 2003 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/11766 Henzinger M, Leonardi S. Scheduling multicasts on unit-capacity trees and meshes. <i>Journal of Computer and System Sciences</i>. 2003;66(3):567-611. doi:<a href="https://doi.org/10.1016/s0022-0000(03)00043-6">10.1016/s0022-0000(03)00043-6</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1016/s0022-0000(03)00043-6 info:eu-repo/semantics/altIdentifier/issn/0022-0000 info:eu-repo/semantics/openAccess