All Maximal Independent Sets and Dynamic Dominance for Sparse Graphs

Details All Maximal Independent Sets and Dynamic Dominance for Sparse Graphs All Maximal Independent Sets and Dynamic Dominance for Sparse Graphs

2004-07-15

arxiv.org/abs/cs/0407036v1

ACM Trans. Algorithms 5(4):A38, 2009

Computer Science

Data Structures and Algorithms

10 pages

Scientific paper

10.1145/1597036.1597042

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.

Affiliated with

Also associated with

No associations

Rating

All Maximal Independent Sets and Dynamic Dominance for Sparse Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with All Maximal Independent Sets and Dynamic Dominance for Sparse Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and All Maximal Independent Sets and Dynamic Dominance for Sparse Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-636275