---
_id: '11925'
abstract:
- lang: eng
  text: "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 NPhard 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\r\nconstant-factor approximation algorithm
    for trees, and an O((log log n)*)-factor approximation algorithm for meshes, where
    n is the number of nodes in the graph. In the online setting, we give the first
    polylogarithrnic competitive online algorithm for tree and mesh topologies. No
    polylogarithmic-competitive algorithm is possible on general network topologies
    [8] and there\r\nexists a polylogarithmic lower bound on the competitive ratio
    of any online algorithm on tree topologies [l]. We prove the same lower bound
    for meshes. "
article_processing_charge: No
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Stefano
  full_name: Leonardi   , Stefano
  last_name: 'Leonardi   '
citation:
  ama: 'Henzinger MH, Leonardi    S. Scheduling multicasts on unit-capacity trees
    and meshes. In: <i>10th Annual ACM-SIAM Symposium on Discrete Algorithms</i>.
    Society for Industrial &#38; Applied Mathematics; 1999:438-447.'
  apa: 'Henzinger, M. H., &#38; Leonardi   , S. (1999). Scheduling multicasts on unit-capacity
    trees and meshes. In <i>10th Annual ACM-SIAM Symposium on Discrete Algorithms</i>
    (pp. 438–447). Baltimore, MD, United States: Society for Industrial &#38; Applied
    Mathematics.'
  chicago: Henzinger, Monika H, and Stefano Leonardi   . “Scheduling Multicasts on
    Unit-Capacity Trees and Meshes.” In <i>10th Annual ACM-SIAM Symposium on Discrete
    Algorithms</i>, 438–47. Society for Industrial &#38; Applied Mathematics, 1999.
  ieee: M. H. Henzinger and S. Leonardi   , “Scheduling multicasts on unit-capacity
    trees and meshes,” in <i>10th Annual ACM-SIAM Symposium on Discrete Algorithms</i>,
    Baltimore, MD, United States, 1999, pp. 438–447.
  ista: 'Henzinger MH, Leonardi    S. 1999. Scheduling multicasts on unit-capacity
    trees and meshes. 10th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA:
    Symposium on Discrete Algorithms, 438–447.'
  mla: Henzinger, Monika H., and Stefano Leonardi   . “Scheduling Multicasts on Unit-Capacity
    Trees and Meshes.” <i>10th Annual ACM-SIAM Symposium on Discrete Algorithms</i>,
    Society for Industrial &#38; Applied Mathematics, 1999, pp. 438–47.
  short: M.H. Henzinger, S. Leonardi   , in:, 10th Annual ACM-SIAM Symposium on Discrete
    Algorithms, Society for Industrial &#38; Applied Mathematics, 1999, pp. 438–447.
conference:
  end_date: 1999-01-19
  location: Baltimore, MD, United States
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 1999-01-17
date_created: 2022-08-18T12:45:50Z
date_published: 1999-01-01T00:00:00Z
date_updated: 2023-02-17T12:08:26Z
day: '01'
extern: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 438-447
publication: 10th Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
  isbn:
  - '0898714346'
publication_status: published
publisher: Society for Industrial & Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Scheduling multicasts on unit-capacity trees and meshes
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '1999'
...