Algorithms for enumerating connected induced subgraphs of a given order
share
Enumerating all connected subgraphs of a given order from graphs is a computationally challenging task. In this paper, we propose two algorithms for enumerating all connected induced subgraphs of a given order from connected undirected graphs. The first algorithm is a variant of a previous well-known algorithm. The algorithm enumerates all connected induced subgraphs of order k in a bottom-up manner. The data structures that lead to unit time element checking and linear space are presented. Different from previous algorithms that either work in a bottom-up manner or in a reverse search manner, an algorithm that enumerates all connected induced subgraphs of order k in a top-down manner by recursively deleting vertices is proposed. The data structures used in the implementation are also presented. The correctness and complexity of the top-down algorithm is analysed and proven. Experimental results show that the variant bottom-up algorithm outperforms the other algorithms for enumerating connected induced subgraphs of small order, and the top-down algorithm is fastest among the state-of-the-art algorithms for enumerating connected induced subgraphs of large order.
READ FULL TEXT