chase@pine.ece.utexas.edu (Craig M. Chase) writes:
> I've not looked at this algorithm to figure out exactly what's going
> on.   Perhaps the explanation is that finding the largest cycle on a
> *weighted* graph is NP-hard, but that finding the largest cycle on a
> graph with unit edge weights is polynomial?  The dependence graph for
> tsort is unweighted, yes?

Finding a cycle in a graph has nothing to do with whether or not the
edges are weighted.  A cycle is a cycle, pure and simple.  Think about
it.

	Mark
--------------------------------------------------------------------
Email: Mark_Weaver@brown.edu           | Brown University
PGP Key: finger mhw@cs.brown.edu       | Dept of Computer Science

------------------------------------------------------------------------------