On-line and dynamic algorithms for shortest path problems

dc.contributor.author	Djidjev, Hristo N.	en
dc.contributor.author	Πάντζιου, Γραμματή Ε.	el
dc.contributor.author	Ζαρολιάγκης, Χρήστος	el
dc.date.accessioned	2015-05-28T20:02:51Z
dc.date.available	2015-05-28T20:02:51Z
dc.date.issued	2015-05-28
dc.identifier.uri	http://hdl.handle.net/11400/11465
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-59042-0_73	en
dc.subject	δυναμικοί αλγόριθμοι
dc.subject	επίπεδο δίγραμμα
dc.subject	δυναμικό περιβάλλον
dc.subject	δομή δεδομένων
dc.subject	παράλληλοι αλγόριθμοι
dc.subject	dynamic algorithms
dc.subject	planar digraph
dc.subject	dynamic environment
dc.subject	Data structures (Computer science)
dc.subject	Parallel algorithms
dc.title	On-line and dynamic algorithms for shortest path problems	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.keywordURI	http://id.loc.gov/authorities/subjects/sh98003394
heal.identifier.secondary	DOI: 10.1007/3-540-59042-0_73
heal.language	en
heal.access	campus
heal.recordProvider	Τεχνολογικό Εκπαιδευτικό Ίδρυμα Αθήνας. Σχολή Τεχνολογικών Εφαρμογών. Τμήμα Μηχανικών Πληροφορικής Τ.Ε.	el
heal.publicationDate	1995-05-02
heal.bibliographicCitation	Djidjev, H., Pantziou, G. and Zaroliagis, C. (1995) On-line and dynamic algorithms for shortest path problems. Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science. 900, pp.193-204. Munich, Germany: Springer Berlin Heidelberg	en
heal.abstract	We describe algorithms for finding shortest paths and distances in a planar digraph which exploit the particular topology of the input graph. An important feature of our algorithms is that they can work in a dynamic environment, where the cost of any edge can be changed or the edge can be deleted. Our data structures can be updated after any such change in only polylogarithmic time, while a single-pair query is answered in sublinear time. We also describe the first parallel algorithms for solving the dynamic version of the shortest path problem.	en
heal.publisher	Springer Berlin Heidelberg	en
heal.fullTextAvailability	true
heal.conferenceName	Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science	en
heal.conferenceItemType	full paper