An algorithm with improved delay for enumerating connected induced subgraphs of a large cardinality

12/14/2021

∙

by   Shanshan Wang, et al.

∙

0

∙

share

Enumerating all connected induced subgraphs of a given order k is a computationally difficult problem. Elbassioni has proposed an algorithm based on reverse search with a delay of O(k· min{(n-k),kΔ}·(k(Δ+logk)+logn)), where n is the number of vertices and Δ is the maximum degree of input graph <cit.>. In this short note, we present an algorithm with an improved delay of O(k· min{(n-k),kΔ}·(klogΔ+logn)) by introducing a new neighborhood definition. This also improves upon the current best delay bound O(k^2Δ)<cit.> for this problem for large k.