Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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: http://imgur.com/mGVlX.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).

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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).

share|improve this answer
    
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? –  russtbarnacle Apr 28 '10 at 20:21
    
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. –  Dylan Thurston Apr 28 '10 at 20:29
    
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? –  russtbarnacle Apr 28 '10 at 21:49
    
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. –  Tony Huynh Apr 28 '10 at 23:12
1  
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.) –  Andrew D. King Oct 26 '10 at 3:40
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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