I have presented our paper on “Listing Maximal Independent Sets with Minimal Space and Bounded Delay” at SPIRE 2017. The conference has been great!
The paper has been a joint work with Alessio Conte, Roberto Grossi, Takeaki Uno and Luca Versari. Below the abstract.
An independent set is a set of nodes in a graph such that no two of them are adjacent. It is maximal if there is no node outside the independent set that may join it. Listing maximal independent sets in graphs can be applied, for example, to sample nodes belonging to different communities or clusters in network analysis and document clustering. The problem has a rich history as it is related to maximal cliques, dominance sets, minimum vertex covers and 3-colorings in graphs. We are interested in reducing the delay, which is the worst-case time between any two consecutively output solutions, and the memory footprint, which is the additional working space behind the read-only input graph.