Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Scheduling multicasts on unit-capacity trees and meshes
 
conference paper

Scheduling multicasts on unit-capacity trees and meshes

Henzinger, Monika R.  
•
Leonardi, Stefano
1999
Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms

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 online 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)2)-factor approximation algorithm for meshes, where n is the number of nodes in the graph. 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 and there exists a polylogarithmic lower bound on the competitive ratio of any online algorithm on tree topologies. We prove the same lower bound for meshess.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

HenzingerL99.pdf

Access type

openaccess

Size

1.24 MB

Format

Adobe PDF

Checksum (MD5)

35b019db6cf8e1277b70abbfc0a5dc7b

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés