2004/10/17 by Sara Cohen, Cohen, Sara, Yehoshua Sagiv +1
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.1.3 #F.2 #FOS: Computer and information sciences #G.2.2 #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0410039
arxiv created 2004/10/17 · openalex publication_date 2004/10/17 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The problem of computing all maximal induced subgraphs of a graph G that have a graph property P, also called the maximal P-subgraphs problem, is considered. This problem is studied for hereditary, connected-hereditary and rooted-hereditary graph properties. The maximal P-subgraphs problem is reduced to restricted versions of this problem by providing algorithms that solve the general problem, assuming that an algorithm for a restricted version is given. The complexity of the algorithms are analyzed in terms of total polynomial time, incremental polynomial time and the complexity class P-enumerable. The general results presented allow simple proofs that the maximal P-subgraphs problem can be solved efficiently (in terms of the input and output) for many different properties.