Timeline for Graph algorithm to find all subgraphs that connect N arbitrary vertices
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 14, 2011 at 14:28 | comment | added | user16446 | I am not sure whether you are looking only for (cardinality) minimal such subgraphs -those are Steiner trees - or for all subgraph connecting selected vertices - you can expect to have an incredible amount of such graphs. The paper cited is wrong (but not that hard to repair) and claims to enumerate all Steiner subgraph. | |
| Oct 26, 2010 at 3:40 | comment | added | Andrew D. King | russtbarnacle, a Steiner tree in geometry is a slightly different concept than a Steiner tree in a graph, and what you're looking for is indeed a Steiner tree in a graph. (The Wikipedia page on Steiner trees describes both.) | |
| Oct 25, 2010 at 21:04 | history | edited | Tony Huynh | CC BY-SA 2.5 |
deleted 125 characters in body
|
| Apr 29, 2010 at 10:20 | vote | accept | russtbarnacle | ||
| Apr 28, 2010 at 23:12 | comment | added | Tony Huynh | Given a graph G and a subset of terminal vertices X of G, a Steiner tree is a connected subgraph of G which contains X. Thus, you simply want to enumerate all Steiner trees where X is your set of blue vertices. And yes, the Steiner nodes are nodes in the original graph which are not terminal nodes. | |
| Apr 28, 2010 at 21:49 | comment | added | russtbarnacle | 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? | |
| Apr 28, 2010 at 20:29 | comment | added | Dylan Thurston | You're a little vague on exactly what kind of subgraphs you're looking for, but the examples in your image seem to be including intermediate vertices. | |
| Apr 28, 2010 at 20:21 | comment | added | russtbarnacle | 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? | |
| Apr 28, 2010 at 18:46 | history | answered | Tony Huynh | CC BY-SA 2.5 |