Efficient sequential and parallel algorithms for the negative cycle problem

dc.contributor.author	Καββαδίας, Δημήτριος	el
dc.contributor.author	Πάντζιου, Γραμματή Ε.	el
dc.contributor.author	Σπυράκης, Παύλος	el
dc.contributor.author	Ζαρολιάγκης, Χρήστος	el
dc.date.accessioned	2015-05-29T18:44:37Z
dc.date.issued	2015-05-29
dc.identifier.uri	http://hdl.handle.net/11400/11890
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-58325-4_190	en
dc.subject	παράλληλοι αλγόριθμοι
dc.subject	αρνητικός κύκλος
dc.subject	επίπεδο δίγραμμα
dc.subject	Parallel algorithms
dc.subject	negative cycle
dc.subject	planar digraph
dc.title	Efficient sequential and parallel algorithms for the negative cycle problem	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/sh98003394
heal.identifier.secondary	DOI: 10.1007/3-540-58325-4_190
heal.dateAvailable	10000-01-01
heal.language	en
heal.access	forever
heal.recordProvider	Τεχνολογικό Εκπαιδευτικό Ίδρυμα Αθήνας. Σχολή Τεχνολογικών Εφαρμογών. Τμήμα Μηχανικών Πληροφορικής Τ.Ε.	el
heal.publicationDate	1994-08-25
heal.bibliographicCitation	Kavvadias, D., Pantziou, G., Spirakis, P. and Zaroliagis, C. (1994) Efficient sequential and parallel algorithms for the negative cycle problem. Proceedings of the 5th International Symposium, ISAAC '94. 834, pp.270-278. Beijing, China: Springer Berlin Heidelberg	en
heal.abstract	We present here an algorithm for detecting (and outputting, if exists) a negative cycle in an n-vertex planar digraph G with real edge weights. Its running time ranges from O(n) up to O(n 1.5 log n) as a certain topological measure of G varies from 1 up to Θ(n). Moreover, an efficient CREW PRAM implementation is given. Our algorithm applies also to digraphs whose genus γ is o(n).	en
heal.publisher	Springer Berlin Heidelberg	en
heal.fullTextAvailability	true
heal.conferenceName	Proceedings of the 5th International Symposium, ISAAC '94	en
heal.conferenceItemType	full paper