Dynamic tree routing under the “matching with consumption” model

dc.contributor.author	Πάντζιου, Γραμματή Ε.	el
dc.contributor.author	Roberts, Alan	en
dc.contributor.author	Συμβώνης, Αντώνιος	el
dc.date.accessioned	2015-05-28T19:50:52Z
dc.date.available	2015-05-28T19:50:52Z
dc.date.issued	2015-05-28
dc.identifier.uri	http://hdl.handle.net/11400/11461
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ηνωμένες Πολιτείες	*
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/3.0/us/	*
dc.source	http://link.springer.com/chapter/10.1007%2FBFb0009504	en
dc.subject	δυναμική δρομολόγηση
dc.subject	δρομολόγηση μοντέλου
dc.subject	αλγόριθμος
dc.subject	ανάλυση
dc.subject	dynamic routing
dc.subject	routing model
dc.subject	algorithm
dc.subject	analysis
dc.title	Dynamic tree routing under the “matching with consumption” model	en
heal.type	conferenceItem
heal.classification	Επιστήμες
heal.classification	Πληροφορική
heal.classification	Science
heal.classification	Computer science
heal.classificationURI	N/A-Επιστήμες
heal.classificationURI	N/A-Πληροφορική
heal.classificationURI	http://skos.um.es/unescothes/C03532
heal.classificationURI	http://skos.um.es/unescothes/C00750
heal.identifier.secondary	DOI: 10.1007/BFb0009504
heal.language	en
heal.access	campus
heal.recordProvider	Τεχνολογικό Εκπαιδευτικό Ίδρυμα Αθήνας. Σχολή Τεχνολογικών Εφαρμογών. Τμήμα Μηχανικών Πληροφορικής Τ.Ε.	el
heal.publicationDate	1996-12-16
heal.bibliographicCitation	Pantziou, G., Roberts, A. and Symvonis, A. (1996) Dynamic tree routing under the “matching with consumption” model. Proceedings of the 7th International Symposium, ISAAC '96. 1178, pp.275-284. Osaka, Japan: Springer Berlin Heidelberg	en
heal.abstract	In this paper we present an extensive study of dynamic routing on trees under the “matching with consumption” routing model. We present an asymptotically optimal on-line algorithm which routes k packets to their destination within d(k−1) + d · 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−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.	en
heal.publisher	Springer Berlin Heidelberg	en
heal.fullTextAvailability	true
heal.conferenceName	Proceedings of the 7th International Symposium, ISAAC '96	en
heal.conferenceItemType	full paper