2024/04/19 by Chenglong Xiao, Xiao, Chenglong, Chengyong Mao +3
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2404.12559
openalex publication_date 2024/04/19 · openalex created_date 2024/04/23 · openalex updated_date 2026/07/28
The problem of enumerating connected subgraphs of a given size in a graph has been extensively studied in recent years. In this paper, we propose an algorithm with a delay of O(kΔ) for enumerating all connected induced subgraphs of size k in an undirected graph G=(V, E), where k and Δ are respectively the size of subgraphs and the maximum degree of G. The algorithm requires a preprocessing step of O(|V| + |E|) time to compute a depth-first search traversal order. The proposed algorithm improves upon the current best delay bound O(k2Δ) for the connected induced subgraph enumeration problem in the literature.