title: Efficiently find all connected induced subgraphs
body: <p>Is there an efficient(*) algorithm to find all the connected (induced) subgraphs of a connected undirected vertex-labelled graph?</p>
  
  <p>(*) I appreciate that, in the general case, any such algorithm may have O(2^n) complexity because, for a clique (Kn), there are 2^n connected subgraphs.  However, the graphs I'm typically dealing with will have far fewer connected subgraphs, so I'm looking for a way to generate them without having to consider all 2^n subgraphs and throw away those that aren't connected (as in the solution to <a href="https://stackoverflow.com/questions/5984531/subgraph-enumeration">this question</a>).</p>
  
  <p>An algorithm that has running time that's linear in the number of the solutions (i.e. it can generate the solutions directly from the structure of the graph without wasting time considering all the non-solutions) would obviously be ideal.  An additional step that's polynomial in the number of nodes would be fine too (e.g. pre-computing the transitive closure of the graph - not that I think that would help in this case).  </p>
  
  <p>Alternatively, a proof that there is no such solution would at least put me out of my misery.</p>