most recent 30 from http://mathoverflow.net 2013-05-20T02:33:34Z http://mathoverflow.net/feeds/user/5692 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/22884/graph-algorithm-to-find-all-subgraphs-that-connect-n-arbitrary-vertices russtbarnacle 2010-04-28T18:01:15Z 2011-07-14T14:28:39Z

<p>I have an graph with the following attributes:</p> <ul> <li>Undirected</li> <li>Not weighted </li> <li>Each vertex has a minimum of 2 and maximum of 6 edges connected to it. </li> <li>Vertex count will be &lt; 100</li> <li>Graph is static and no vertices/edges can be added/removed or edited.</li> </ul> <p>I'm looking for <strong>all</strong> subgraphs between a random subset of the vertices (at least 2). </p> <p>I've created a (warning! programmer art) animated gif to illustrate what i'm trying to achieve: <a href="http://imgur.com/mGVlX.gif" rel="nofollow">http://imgur.com/mGVlX.gif</a></p> <p>My end goal is to have a set of subgraphs that allow moving from one of the subset vertices (blue nodes) and reach <strong>any</strong> of the other subset vertices (blue nodes).</p>

http://mathoverflow.net/questions/22884/graph-algorithm-to-find-all-subgraphs-that-connect-n-arbitrary-vertices/22888#22888 russtbarnacle 2010-04-28T21:49:23Z 2010-04-28T21:49:23Z

I'm rapidly moving out of my depth it appears but my understanding was that Steiner trees create vertices that would not of been in the original graph. Is a Steiner node (in relation to graphs) in fact any node that is in the original graph but not a terminal node?

http://mathoverflow.net/questions/22884/graph-algorithm-to-find-all-subgraphs-that-connect-n-arbitrary-vertices/22888#22888 russtbarnacle 2010-04-28T20:21:58Z 2010-04-28T20:21:58Z

My understanding was that Steiner trees introduce intermediate vertices and edges? My graph is fixed, does this algorithm give the subgraphs without adding vertices or edges?