Many-to-many routing on trees via matchings

dc.contributor.author	Πάντζιου, Γραμματή Ε.	el
dc.contributor.author	Roberts, Alan	en
dc.contributor.author	Συμβώνης, Αντώνιος	el
dc.date.accessioned	2015-05-25T18:54:19Z
dc.date.available	2015-05-25T18:54:19Z
dc.date.issued	2015-05-25
dc.identifier.uri	http://hdl.handle.net/11400/11144
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ηνωμένες Πολιτείες	*
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/3.0/us/	*
dc.source	http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.1095	en
dc.subject	μοντέλο δρομολόγησης
dc.subject	αλγόριθμος
dc.subject	ταιριάσματα
dc.subject	routing model
dc.subject	algorithm
dc.subject	matchings
dc.title	Many-to-many routing on trees via matchings	en
heal.type	journalArticle
heal.classification	Τεχνολογία
heal.classification	Πληροφορική
heal.classification	Technology
heal.classification	Computer science
heal.classificationURI	N/A-Τεχνολογία
heal.classificationURI	N/A-Πληροφορική
heal.classificationURI	http://id.loc.gov/authorities/subjects/sh85133147
heal.classificationURI	http://skos.um.es/unescothes/C00750
heal.identifier.secondary	DOI: 10.1.1.31.1095
heal.language	en
heal.access	free
heal.recordProvider	Τεχνολογικό Εκπαιδευτικό Ίδρυμα Αθήνας. Σχολή Τεχνολογικών Εφαρμογών. Τμήμα Μηχανικών Πληροφορικής Τ.Ε.	el
heal.publicationDate	1997-10-20
heal.bibliographicCitation	Pantziou,G., Roberts, A. and Symvonis, A. (1997) Many-to-many routing on trees via matchings. Theoretical Computer Science. [Online] 185 (2). pp.347-377. Available from: http://www.sciencedirect.com [Accessed 25/05/2015]	en
heal.abstract	In this paper we present an extensive study of many-to-many routing on trees under the matching routing model. Our study includes on-line and off-line algorithms. We present an asymptotically optimal on-line algorithm which routes k packets to their destination within d(k \Gamma 1) + d \Delta dist routing steps, where d is the degree of tree T on which the routing takes place and dist is the maximum distance any packet has to travel. We also present an off-line algorithm that solves the same problem within 2(k \Gamma 1)+dist steps. The analysis of our algorithms is based on the establishment of a close relationship between the matching and the hot-potato routing models that allows us to apply tools which were previously used exclusively in the analysis of hot-potato routing.	en
heal.publisher	Elsevier	en
heal.journalName	Theoretical Computer Science	en
heal.journalType	peer-reviewed
heal.fullTextAvailability	true