Efficient Sequential and Parallel Algorithms for the Negative Cycle Problem

Dartmouth Technical Report PCS-TR94-206

	Dimitrios Kavvadias
	Grammati E. Pantziou
	Paul G. Spirakis
	Christos D. Zaroliagis

Date:  1994

URL (PDF): <http://www.cs.dartmouth.edu/reports/TR94-206.pdf> (616KB)

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
 $\Theta(n)$.  Moreover, an efficient CREW PRAM implementation is
 given.  Our algorithm applies also to digraphs whose genus $\gamma$ is
 $o(n)$.