Computing shortest paths and distances in planar graphs

dc.contributor.author	Djidjev, Hristo N.	en
dc.contributor.author	Πάντζιου, Γραμματή Ε.	el
dc.contributor.author	Ζαρολιάγκης, Χρήστος	el
dc.date.accessioned	2015-05-29T19:20:43Z
dc.date.issued	2015-05-29
dc.identifier.uri	http://hdl.handle.net/11400/11905
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%2F3-540-54233-7_145	en
dc.subject	επίπεδα γραφήματα
dc.subject	αλγόριθμοι
dc.subject	επεξεργαστές
dc.subject	προεπεξεργασία
dc.subject	αιώρα αποσύνθεση
dc.subject	planar graphs
dc.subject	algorithms
dc.subject	processors
dc.subject	preprocessing
dc.subject	hammock decomposition
dc.title	Computing shortest paths and distances in planar graphs	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/3-540-54233-7_145
heal.dateAvailable	10000-01-01
heal.language	en
heal.access	forever
heal.recordProvider	Τεχνολογικό Εκπαιδευτικό Ίδρυμα Αθήνας. Σχολή Τεχνολογικών Εφαρμογών. Τμήμα Μηχανικών Πληροφορικής Τ.Ε.	el
heal.publicationDate	1991-07-08
heal.bibliographicCitation	Djidjev, H., Pantziou, G. and Zaroliagis, C. (1991) Computing shortest paths and distances in planar graphs. Proceedings of the 18th International Colloquium. 510, pp.327-338. Madrid, Spain: Springer Berlin Heidelberg	en
heal.abstract	We provide here efficient sequential and parallel solutions to the following problem: given a planar digraph G (with real edge weights but no negative cycles) for preprocessing, answer on-line queries requesting the shortest distance (or path) between any two vertices in G. Our algorithms for preprocessing need O(n log n + q 2) space and O(n log n + q 2) sequential time. (Here q is the cardinality of a set of faces of a planar embedding of G that cover all vertices.)A parallel implementation on a CREW PRAM needs also O(n log n + q 2) space and runs in O(log2 n) time using O(n + M(q)) processors (where M(q) is the number of processors required to multiply two q × q matrices in O(log q) time), provided that the q faces are given by the input.This enables us to achieve O(log n) time using a single processor for a “distance” query, or O(L + log n) time for a “path” query (where L is the length of the path). Note that this is a considerable improvement over previous results in the case where q = o(n). Our techniques are based on the hammock decomposition of a planar digraph and the use of separators for computing quickly internal distances in the graph. Several other results are achieved. For outerplanar graphs, our algorithms preprocess the graph in O(n logn) space and run either in O(n log n) sequential time, or in O(log2 n) time using O(n) processors on a CREW PRAM. A “distance” query can be answered in O(log n) time using a single processor. A “path” query is answered in O(L + log n) time. An optimal solution is given in the case of trees. We achieve O(1) time per “distance” query andwe need O(n) sequential time, or O(log n) time and O(n/log n) processors (on an EREW PRAM) for preprocessing. A “path” query is answered in O(L) time.	en
heal.publisher	Springer Berlin Heidelberg	en
heal.fullTextAvailability	false
heal.conferenceName	Proceedings of the 18th International Colloquium	en
heal.conferenceItemType	full paper