Fast algorithms for maintaining shortest paths in outerplanar and planar digraphs

dc.contributor.author	Djidjev, Hristo N.	en
dc.contributor.author	Πάντζιου, Γραμματή Ε.	el
dc.contributor.author	Ζαρολιάγκης, Χρήστος	el
dc.date.accessioned	2015-05-28T20:28:30Z
dc.date.available	2015-05-28T20:28:30Z
dc.date.issued	2015-05-28
dc.identifier.uri	http://hdl.handle.net/11400/11475
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/3-540-60249-6_51	en
dc.subject	γρήγοροι αλγόριθμοι
dc.subject	επίπεδα διγράμματα
dc.subject	προεπεξεργασία
dc.subject	δομή δεδομένων
dc.subject	Fast algorithms
dc.subject	planar digraphs
dc.subject	preprocessing
dc.subject	Data structures (Computer science)
dc.title	Fast algorithms for maintaining shortest paths in outerplanar and planar digraphs	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.keywordURI	http://id.loc.gov/authorities/subjects/sh85035862
heal.identifier.secondary	DOI: 10.1007/3-540-60249-6_51
heal.language	en
heal.access	campus
heal.recordProvider	Τεχνολογικό Εκπαιδευτικό Ίδρυμα Αθήνας. Σχολή Τεχνολογικών Εφαρμογών. Τμήμα Μηχανικών Πληροφορικής Τ.Ε.	el
heal.publicationDate	1995-08-22
heal.bibliographicCitation	Djidjev, H., Pantziou, G. and Zaroliagis, C. (1995) Fast algorithms for maintaining shortest paths in outerplanar and planar digraphs. Proceedings of the 10th International Conference, FCT '95. 965, pp.191-200. Dresden, Germany: Springer Berlin Heidelberg	en
heal.abstract	We present algorithms for maintaining shortest path information in dynamic outerplanar digraphs with sublogarithmic query time. By choosing appropriate parameters we achieve continuous trade-offs between the preprocessing, query, and update times. Our data structure is based on a recursive separator decomposition of the graph and it encodes the shortest paths between the members of a properly chosen subset of vertices. We apply this result to construct improved shortest path algorithms for dynamic planar digraphs.	en
heal.publisher	Springer Berlin Heidelberg	en
heal.fullTextAvailability	true
heal.conferenceName	Proceedings of the 10th International Conference, FCT '95	en
heal.conferenceItemType	full paper