δείτε την πρωτότυπη σελίδα τεκμηρίου στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
Computing shortest paths and distances in planar graphs
(EN)
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)
Proceedings of the 18th International Colloquium
(EN)
*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.
Βοηθείστε μας να κάνουμε καλύτερο το OpenArchives.gr.
