abstract
the linear induced matching width (lmim-width) of a graph is a
width parameter defined by using the notion of branch-decompositions
of a set function on ternary trees. in this paper we study outputpolynomial enumeration algorithms on graphs of bounded lmim-width
and graphs of bounded local lmim-width. in particular, we show that
all 1-minimal and all 1-maximal pσ, ρq-dominating sets, and hence all
minimal dominating sets, of graphs of bounded lmim-width can be
enumerated with polynomial (linear) delay using polynomial space.
furthermore, we show that all minimal dominating sets of a unit square
graph can be enumerated in incremental polynomial time.