%T Efficient Sequential and Parallel Algorithms for the Negative Cycle Problem
%A Dimitrios Kavvadias
%A Grammati E. Pantziou
%A Paul G. Spirakis
%A Christos D. Zaroliagis
%R Technical Report PCS-TR94-206
%I Dartmouth College, Computer Science
%C Hanover, NH
%D  1994
%U http://www.cs.dartmouth.edu/reports/TR94-206.pdf
%X
 	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
 $\Theta(n)$.  Moreover, an efficient CREW PRAM implementation is
 given.  Our algorithm applies also to digraphs whose genus $\gamma$ is
 $o(n)$.