2021/12/14 by Shanshan Wang, Wang, Shanshan, Chenglong Xiao +3
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Genome Rearrangement Algorithms #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2112.07204
openalex publication_date 2021/12/14 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
The problem of enumerating all connected induced subgraphs of a given order k from a given graph arises in many practical applications: bioinformatics, information retrieval, processor design,to name a few. The upper bound on the number of connected induced subgraphs of order k is n⋅\frac(eΔ)k(Δ-1)k, where Δ is the maximum degree in the input graph G and n is the number of vertices in G. In this short communication, we first introduce a new neighborhood operator that is the key to design reverse search algorithms for enumerating all connected induced subgraphs of order k. Based on the proposed neighborhood operator, three algorithms with delay of O(k⋅ min\(n-k),kΔ\⋅(klogΔ+logn)), O(k⋅ min\(n-k),kΔ\⋅ n) and O(k2⋅ min\(n-k),kΔ\⋅ min\k,Δ\) respectively are proposed. The first two algorithms require exponential space to improve upon the current best delay bound O(k2Δ)\cite4 for this problem in the case k>\fracnlogΔ-logn-Δ+√nlognlogΔlogΔ and k>(n2)/(n+Δ) respectively.