Efficient sequential and parallel algorithms for the negative cycle problem

Καββαδίας, Δημήτριος; Πάντζιου, Γραμματή Ε.; Σπυράκης, Παύλος; Ζαρολιάγκης, Χρήστος

Ημερομηνία Δημοσίευσης: 1994-08-25

Τύπος Τεκμηρίου: Δημοσίευση σε συνέδριο

Όνομα Συνεδρίου: Proceedings of the 5th International Symposium, ISAAC '94

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).

Πηγή: http://link.springer.com/chapter/10.1007%2F3-540-58325-4_190

Θέμα: Επιστήμες, Πληροφορική, Science, Computer science

Εμφάνιση πλήρους εγγραφής