Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
  Lokale TagsFreigabegeschichteDetailsÜbersicht

Freigegeben
Bericht

Scheduling multicasts on unit-capacity trees and meshes

MPG-Autoren
/persons/resource/persons44913

Leonardi,  Stefano
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)

MPI-I-98-1-015.pdf
(beliebiger Volltext), 393KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Henzinger, M. R., & Leonardi, S.(1998). Scheduling multicasts on unit-capacity trees and meshes (MPI-I-1998-1-015). Saarbrücken: Max-Planck-Institut für Informatik.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-0014-7BC5-5
Zusammenfassung
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 O((log log n)^2)-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 [Bartal,Fiat,Leonardi, 96], and there exists a polylogarithmic lower bound on the competitive ratio of any online algorithm on tree topologies [Awerbuch,Azar,Fiat,Leighton, 96]. We prove the same lower bound for meshes.