Quickest paths

dc.contributor.author	Καγάρης, Δημήτριος	el
dc.contributor.author	Πάντζιου, Γραμματή Ε.	el
dc.contributor.author	Τραγούδας, Σπύρος	el
dc.contributor.author	Ζαρολιάγκης, Χρήστος	el
dc.date.accessioned	2015-05-28T20:16:06Z
dc.date.issued	2015-05-28
dc.identifier.uri	http://hdl.handle.net/11400/11471
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ηνωμένες Πολιτείες	*
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/3.0/us/	*
dc.source	http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=375479&abstractAccess=no&userType=inst	en
dc.subject	υπολογιστική πολυπλοκότητα
dc.subject	δομή δεδομένων
dc.subject	κατευθυνόμενα γραφήματα
dc.subject	επιχειρησιακή έρευνα
dc.subject	παράλληλοι αλγόριθμοι
dc.subject	τηλεπικοινωνιακά δίκτυα
dc.subject	πρόβλημα του πλανόδιου πωλητή
dc.subject	Computational complexity
dc.subject	Data structures (Computer science)
dc.subject	Directed graphs
dc.subject	Operations research
dc.subject	Parallel algorithms
dc.subject	telecommunication networks
dc.subject	travelling salesman problems
dc.title	Quickest paths	en
heal.type	conferenceItem
heal.secondaryTitle	parallelization and dynamization	en
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.keywordURI	http://id.loc.gov/authorities/subjects/sh85029473
heal.keywordURI	http://id.loc.gov/authorities/subjects/sh85035862
heal.keywordURI	http://id.loc.gov/authorities/subjects/sh85038262
heal.keywordURI	http://zbw.eu/stw/descriptor/15483-0
heal.keywordURI	http://id.loc.gov/authorities/subjects/sh98003394
heal.identifier.secondary	DOI: 10.1109/HICSS.1995.375479
heal.dateAvailable	10000-01-01
heal.language	en
heal.access	forever
heal.recordProvider	Τεχνολογικό Εκπαιδευτικό Ίδρυμα Αθήνας. Σχολή Τεχνολογικών Εφαρμογών. Τμήμα Μηχανικών Πληροφορικής Τ.Ε.	el
heal.publicationDate	1995-01-03
heal.bibliographicCitation	Kagaris, D., Pantziou, G., Tragoudas, S. and Zaroliagis, C. (1995) Quickest paths: parallelization and dynamization. Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS-28). 2, pp.39-40. Wailea, HI: IEEE	en
heal.abstract	Let N=(V,E,c,l) be a network, where G=(V,E) is a directed graph (\|V\|=n and \|E\|=m), c(e)>0 is the capacity and l(e)⩾0 is the lead time for each edge e∈E. The transmission time to send σ units of data from a given source s to a destination t using path p is T(σ,p) = l(p) + σ/c(p), where l(p) is the sum of the lead times of the edges in p, and c(p) is the minimum capacity of the edges in p. The quickest path problem is to find a path of minimum transmission time to transmit the σ units of data from s to t. The problem has applications to fast data transmissions in communication networks. We present parallel algorithms for solving the quickest path problem in the case where the network is sparse [i.e. m=O(n)]. We also give algorithms for solving the dynamic quickest path problem. In this problem, the network, the lead times and the capacities on its edges, as well as the amount of data to be transmitted, change over time. The goal is to build a data structure so that one can very quickly compute the quickest path to transmit a given amount of data from any node s to any node t and also, after a dynamic change (edge lead time or edge capacity modification, or edge deletion) on the input network, to be able to update the data structure in an appropriately short time. Furthermore, we improve upon the best sequential result for the single pair quickest path problem which needs O(rm+rn log n) time, where r is the number of distinct edge capacities.	en
heal.publisher	IEEE	en
heal.fullTextAvailability	true
heal.conferenceName	Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS-28)	en
heal.conferenceItemType	full paper