Efficient enumeration of maximal k-degenerate induced subgraphs of a chordal graph

摘要

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.omega(G)) for any n-vertex chordal graph with m edges, where omega(G) <= n is the maximum size of a clique in G. Degeneracy is a well known sparsity measure, and k-degenerate subgraphs are a notion of sparse subgraphs, which generalizes other problems such as independent sets (0-degenerate subgraphs) and forests (1-degenerate subgraphs).