Re: [boost] BGL: like transitive_closure, but not exactly

From: Vladimir Prus (ghost_at_[hidden])
Date: 2002-01-15 04:17:16

Hi David,

> By the way, I have a solution, and it's probably sufficiently fast for my
> purposes:

> ----- Original Message -----
> From: "Swarat Chaudhuri" <swarat_c_at_[hidden]>
> Newsgroups: comp.theory
> Sent: Friday, January 11, 2002 8:32 PM
> Subject: Re: like transitive closure, but not exactly
>
> > The problem, as you state it, is less than trivial. For each edge
> > (u,v), remove u, and do a BFS from v. For all vertices s that are
> > reached by the BFS, output ((u,v),s).
> >
> > Time taken = O((|V|+|E|)*|E|)

The *solution* is trivial and it was quickly arrived at when I was discussing 
this problem with a colleague yesterday. But is it true that no faster 
algorithm exists? This question might be more appropriate in comp.theory, 
though :-)

- Volodya