1
$\begingroup$

I have an graph with the following attributes:

  • Undirected
  • Not weighted
  • Each vertex has a minimum of 2 and maximum of 6 edges connected to it.
  • Vertex count will be < 100
  • Graph is static and no vertices/edges can be added/removed or edited.

I'm looking for all subgraphs between a random subset of the vertices (at least 2).

I've created a (warning! programmer art) animated gif to illustrate what i'm trying to achieve: https://i.stack.imgur.com/Hgaq5.gif

My end goal is to have a set of subgraphs that allow moving from one of the subset vertices (blue nodes) and reach any of the other subset vertices (blue nodes).

$\endgroup$

1 Answer 1

4
$\begingroup$

It looks like the paper

Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals

by Costa Dourado, de Oliveira, and Protti is what you want (available from ScienceDirect). I think the paper gives an algorithm for generating all the minimal (under subgraph inclusion) subgraphs connecting the blue vertices (from which it is easy to obtain all such subgraphs).

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$ Apr 28, 2010 at 20:21
  • $\begingroup$ 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. $\endgroup$ Apr 28, 2010 at 20:29
  • $\begingroup$ 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? $\endgroup$ Apr 28, 2010 at 21:49
  • $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    Apr 28, 2010 at 23:12
  • 1
    $\begingroup$ 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.) $\endgroup$ Oct 26, 2010 at 3:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.