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.sstatic.net/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).

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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).

Improve this answer
$\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$
    – russtbarnacle
    Commented 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$
    – Dylan Thurston
    Commented 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$
    – russtbarnacle
    Commented 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
    Commented 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$
    – Andrew D. King
    Commented Oct 26, 2010 at 3:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .