All Maximal Independent Sets and Dynamic Dominance for Sparse Graphs
<|reference_start|>All Maximal Independent Sets and Dynamic Dominance for Sparse Graphs: We describe algorithms, based on Avis and Fukuda's reverse search paradigm, for listing all maximal independent sets in a sparse graph in polynomial time and delay per output. For bounded degree graphs, our algorithms take constant time per set generated; for minor-closed graph families, the time is O(n) per set, and for more general sparse graph families we achieve subquadratic time per set. We also describe new data structures for maintaining a dynamic vertex set S in a sparse or minor-closed graph family, and querying the number of vertices not dominated by S; for minor-closed graph families the time per update is constant, while it is sublinear for any sparse graph family. We can also maintain a dynamic vertex set in an arbitrary m-edge graph and test the independence of the maintained set in time O(sqrt m) per update. We use the domination data structures as part of our enumeration algorithms.<|reference_end|>
@article{eppstein2004all,
    title={All Maximal Independent Sets and Dynamic Dominance for Sparse Graphs},
    author={David Eppstein},
    journal={ACM Trans. Algorithms 5(4):A38, 2009},
    year={2004},
    doi={10.1145/1597036.1597042},
    archivePrefix={arXiv},
    eprint={cs/0407036},
    primaryClass={cs.DS}
}