2004/07/15 by David Eppstein · 1 citation
Computer Science · #Advanced Graph Theory Research #Circulant graph #Comparability graph #Complement graph #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Dense graph #Graph #Graph power #Independent set #Split graph #Sublinear function #Vertex (graph theory) #cs.DS
paper · pdf · doi:10.1145/1597036.1597042
published as ACM Trans. Algorithms 5(4):A38, 2009 · 10 pages
arxiv created 2004/07/15 · openalex publication_date 2009/10/01 · openalex created_date 2020/12/21 · openalex updated_date 2026/08/05
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 (√m) per update. We use the domination data structures as part of our enumeration algorithms.