Minimum equivalent digraph is probably what you seek. On Fri, Mar 12, 2010 at 10:20 AM, Victor Miller <victorsmiller@gmail.com>wrote:
I've been doing some computations with directed graphs, and I came across the need for the following. I'm sure that it has a name, and that there are good (i.e. efficient) algorithms for this out there, if I could only guess the name.
Let D be a directed graph. If we have a subgraph D' of D (same vertex set, subset of the edges), I'll say that D' ==> D if for every edges from v-->w in D there is a path from v to w in D'. I'd like to find a minimal D' so that D' ==> D (i.e., if we delete any edge from D' it no longer has this property). I suspect, by the general law of perversity, that finding the minimum (i.e. the minimal D' with the least edges) is probably hard in general. So does anyone know what this is called?
Victor
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Check out Golly at http://golly.sf.net/