Generating All Maximal Induced Subgraphs for Hereditary, Connected-Hereditary and Rooted-Hereditary Properties
| dc.creator | Cohen, Sara | |
| dc.creator | Sagiv, Yehoshua | |
| dc.date | 2004-10-17 | |
| dc.date.accessioned | 2026-07-07T03:21:52Z | |
| dc.date.available | 2026-07-07T03:21:52Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/cs/0410039 | |
| dc.identifier | http://arxiv.org/abs/cs/0410039 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/32375 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Discrete Mathematics | |
| dc.subject | G.2.2; F.2; F.1.3 | |
| dc.title | Generating All Maximal Induced Subgraphs for Hereditary, Connected-Hereditary and Rooted-Hereditary Properties | |
| dc.type | text |