[BGL] Survivability Network Design Problem

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

[BGL] Survivability Network Design Problem

Alejandro Aragón
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.

Alejandro Aragon

_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: [BGL] Survivability Network Design Problem

Doug Gregor-2

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
_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users