In this paper, we consider the problem of listing the maximal k-degenerate induced subgraphs of a chordal graph, and propose an output-sensitive algorithm using delay O(m\cdot \omega (G)) for any n-vertex chordal graph with m edges, where \omega (G) \le n is the maximum size of a clique in G. The problem generalizes that of enumerating maximal independent sets and maximal induced forests, which correspond to respectively 0-degenerate and 1-degenerate subgraphs.
Efficient enumeration of maximal k-degenerate subgraphs in a chordal graph
Conte, Alessio;
2017-01-01
Abstract
In this paper, we consider the problem of listing the maximal k-degenerate induced subgraphs of a chordal graph, and propose an output-sensitive algorithm using delay O(m\cdot \omega (G)) for any n-vertex chordal graph with m edges, where \omega (G) \le n is the maximum size of a clique in G. The problem generalizes that of enumerating maximal independent sets and maximal induced forests, which correspond to respectively 0-degenerate and 1-degenerate subgraphs.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
