12 Mar
2010
12 Mar
'10
11:20 a.m.
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