Please use this identifier to cite or link to this item:
Title: Quickest paths
Alternative title / Subtitle: parallelization and dynamization
Authors: Καγάρης, Δημήτριος
Πάντζιου, Γραμματή Ε.
Τραγούδας, Σπύρος
Ζαρολιάγκης, Χρήστος
Item type: Conference publication
Conference Item Type: Full Paper
Keywords: υπολογιστική πολυπλοκότητα;δομή δεδομένων;κατευθυνόμενα γραφήματα;επιχειρησιακή έρευνα;παράλληλοι αλγόριθμοι;τηλεπικοινωνιακά δίκτυα;πρόβλημα του πλανόδιου πωλητή;Computational complexity;Data structures (Computer science);Directed graphs;Operations research;Parallel algorithms;telecommunication networks;travelling salesman problems
Subjects: Επιστήμες
Computer science
Issue Date: 28-May-2015
Publisher: IEEE
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.
Language: English
Citation: 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
Conference: Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS-28)
Access scheme: Embargo
License: Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ηνωμένες Πολιτείες
Appears in Collections:Δημοσιεύσεις

Files in This Item:
File Description SizeFormat 
  Restricted Access
260.97 kBAdobe PDFView/Open Request a copy

This item is licensed under a Creative Commons License Creative Commons