Minimum Eccentricity Multicast Trees
We consider the problem of constructing a multicast tree that connects a group of source nodes to a group of sink nodes (receivers) and minimizes the maximum end-to-end delay between any pair of source/sink nodes. This is known as the \emphminimum eccentricity multicast tree problem, and is directly...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2001-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/278/pdf |
| _version_ | 1797270200099274752 |
|---|---|
| author | David Krumme Paraskevi Fragopoulou |
| author_facet | David Krumme Paraskevi Fragopoulou |
| author_sort | David Krumme |
| collection | DOAJ |
| description | We consider the problem of constructing a multicast tree that connects a group of source nodes to a group of sink nodes (receivers) and minimizes the maximum end-to-end delay between any pair of source/sink nodes. This is known as the \emphminimum eccentricity multicast tree problem, and is directly related to the quality of service requirements of real multipoint applications. We deal directly with the problem in its general form, meaning that the sets of source and sink nodes need not be overlapping nor disjoint. The main contribution of this work is a polynomial algorithm for this problem on general networks which is inspired by an innovative method that uses geometric relationships on the xy-plane. |
| first_indexed | 2024-04-25T02:00:29Z |
| format | Article |
| id | doaj.art-54d91755db16497e869e7ea16f9a410c |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:00:29Z |
| publishDate | 2001-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-54d91755db16497e869e7ea16f9a410c2024-03-07T15:04:11ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502001-01-01Vol. 4 no. 210.46298/dmtcs.278278Minimum Eccentricity Multicast TreesDavid Krumme0Paraskevi Fragopoulou1Department of Electrical and Computer Engineering [Medford MA]Parallélisme, Réseaux, Systèmes, ModélisationWe consider the problem of constructing a multicast tree that connects a group of source nodes to a group of sink nodes (receivers) and minimizes the maximum end-to-end delay between any pair of source/sink nodes. This is known as the \emphminimum eccentricity multicast tree problem, and is directly related to the quality of service requirements of real multipoint applications. We deal directly with the problem in its general form, meaning that the sets of source and sink nodes need not be overlapping nor disjoint. The main contribution of this work is a polynomial algorithm for this problem on general networks which is inspired by an innovative method that uses geometric relationships on the xy-plane.https://dmtcs.episciences.org/278/pdfmulticasteccentricityalgorithmcommunicationsgraphnetwork[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | David Krumme Paraskevi Fragopoulou Minimum Eccentricity Multicast Trees Discrete Mathematics & Theoretical Computer Science multicast eccentricity algorithm communications graph network [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | Minimum Eccentricity Multicast Trees |
| title_full | Minimum Eccentricity Multicast Trees |
| title_fullStr | Minimum Eccentricity Multicast Trees |
| title_full_unstemmed | Minimum Eccentricity Multicast Trees |
| title_short | Minimum Eccentricity Multicast Trees |
| title_sort | minimum eccentricity multicast trees |
| topic | multicast eccentricity algorithm communications graph network [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/278/pdf |
| work_keys_str_mv | AT davidkrumme minimumeccentricitymulticasttrees AT paraskevifragopoulou minimumeccentricitymulticasttrees |