Re: [Boost-users] [BGL] Survivability Network Design Problem

From: Doug Gregor (dgregor_at_[hidden])
Date: 2006-04-10 15:41:37

On Apr 10, 2006, at 11:16 AM, Alejandro Aragón wrote:

> Hello everybody,
>
> I was wondering if anybody had to implement the SNDP problem using
> graphs.  Is there anything in the boost library that deals with this
> problem?  In the SNDP we have to design a graph having certain  
> degree of
> redundancy (cycles in the graph) so if you remove one edge, then  
> you can
> still reach every part in the graph.  Stated in a different way, you
> should be able to have different paths between two vertices in the
> graph.  So far I have seen only algorithms to deal with minimum  
> spanning
> trees.  I appreciate anything related to this problem.

This sounds like it is closely related to the problem of finding  
biconnected components and articulation points. If a graph has no  
articulation points, then it will remain connected even if a vertex  
is destroyed. The BGL has biconnected components and articulation  
points algorithms already.

        Doug