A Polynomial Delay Algorithm for Generating Connected Induced Subgraphs of a Given Cardinality - Elbassioni, Khaled (Journal of Graph Algorithms and Applications, 2015)
We give a polynomial delay algorithm, that for any graph G and positive integer k, enumerates all connected induced subgraphs of G of order k. Our algorithm enumerates each subgraph in at most O((kmin(n−k),k∆)2(∆+logk)) and uses linear space O(n+m), where n and m are respectively the number of vertices and edges of G and ∆ is the maximum degree.