A Polynomial Delay Algorithm for Generating Connected Induced Subgraphs\n of a Given Cardinality

2014/11/09 by Khaled Elbassioni, Elbassioni, Khaled
Computer Science · Engineering · #Advanced Graph Theory Research #Coding theory and cryptography #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1411.2262

openalex publication_date 2014/11/09 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28

Abstract

We give a polynomial delay algorithm, that for any graph G and positive\ninteger k, enumerates all connected induced subgraphs of G of order k.\nOur algorithm enumerates each subgraph in at most\nO((k\min (n-k),k\Δ )²(\Δ+\log k)) and uses linear space O(n+m),\nwhere n and m are respectively the number of vertices and edges of G and\n\Δ is the maximum degree.\n

Related

• Algorithms with improved delay for enumerating connected induced subgraphs of a large cardinality
• An algorithm with a delay of O(kΔ) for enumerating connected induced subgraphs of size k
• A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs
• Polynomial-Delay Enumeration of Large Maximal Matchings
• Enumerating Connected Dominating Sets