Efficient parallel algorithms for shortest paths in planar digraphs

dc.contributor.author	Πάντζιου, Γραμματή Ε.	el
dc.contributor.author	Σπυράκης, Παύλος	el
dc.contributor.author	Ζαρολιάγκης, Χρήστος	el
dc.date.accessioned	2015-05-25T19:52:30Z
dc.date.available	2015-05-25T19:52:30Z
dc.date.issued	2015-05-25
dc.identifier.uri	http://hdl.handle.net/11400/11152
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ηνωμένες Πολιτείες	*
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/3.0/us/	*
dc.source	http://link.springer.com/article/10.1007%2FBF01994878	en
dc.subject	αλγόριθμος
dc.subject	Επίπεδα διγράμματος
dc.subject	συντομότερη διαδρομή
dc.subject	αιώρα αποσύνθεση
dc.subject	συμπαγείς πίνακες δρομολόγησης
dc.subject	παράλληλη συρρίκνωση δέντρου
dc.subject	Algorithm
dc.subject	Planar digraph
dc.subject	shortest path
dc.subject	hammock decomposition
dc.subject	compact routing tables
dc.subject	parallel tree contraction
dc.title	Efficient parallel algorithms for shortest paths in planar digraphs	en
heal.type	journalArticle
heal.classification	Πληροφορική
heal.classification	Μαθηματικά
heal.classification	Computer science
heal.classification	Mathematics
heal.classificationURI	N/A-Πληροφορική
heal.classificationURI	N/A-Μαθηματικά
heal.classificationURI	http://skos.um.es/unescothes/C00750
heal.classificationURI	http://skos.um.es/unescothes/C02437
heal.identifier.secondary	DOI: 10.1007/BF01994878
heal.language	en
heal.access	campus
heal.recordProvider	Τεχνολογικό Εκπαιδευτικό Ίδρυμα Αθήνας. Σχολή Τεχνολογικών Εφαρμογών. Τμήμα Μηχανικών Πληροφορικής Τ.Ε.	el
heal.publicationDate	1992
heal.bibliographicCitation	Pantziou, G., Spirakis, P. and Zaroliagis, C. (1992) Efficient Parallel Algorithms for Shortest Paths Planar Digraphs. BIT Numerical Mathematics. [Online] 32 (2), pp.215-236. Available from: http://link.springer.com [Accessed 25/05/2015]	en
heal.abstract	Efficient parallel algorithms are presented, on the CREW PRAM model, for generating a succinct encoding of all pairs shortest path information in a directed planar graphG with real-valued edge costs but no negative cycles. We assume that a planar embedding ofG is given, together with a set ofq faces that cover all the vertices. Then our algorithm runs inO(log2 n) time and employsO(nq+M(q)) processors (whereM(t) is the number of processors required to multiply twot×t matrices inO(logt) time). Let us note here that wheneverq<n then our processor bound is better than the best previous one (M(n)).O(log2 n) time,n-processor algorithms are presented for various subproblems, including that of generating all pairs shortest path information in a directedouterplanar graph. Our work is based on the fundamental hammock-decomposition technique of G. Frederickson. We achieve this decomposition inO(logn log*n) parallel time by usingO(n) processors. The hammock-decomposition seems to be a fundamental operation that may help in improving efficiency of many parallel (and sequential) graph algorithms.	en
heal.publisher	Kluwer Academic Publishers	en
heal.journalName	BIT Numerical Mathematics	en
heal.journalType	peer-reviewed
heal.fullTextAvailability	true