**Subject:** Re: CVS question

**To:** Craig M. Chase *<chase@pine.ece.utexas.edu>*

**From:** None *<Mark_Weaver@brown.edu>*

**List:** current-users

**Date:** 12/15/1993 19:23:29
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
------------------------------------------------------------------------------