# Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width

arXiv: https://arxiv.org/abs/1509.03753 · HTML: https://mlsanity.com/paper/1509.03753/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2015.

## Built on by (most cited first, 1 of 1)

- [Diversity in Kemeny Rank Aggregation: A Parameterized Approach](https://mlsanity.com/paper/2105.09413/) (2021)

## Abstract (arXiv)

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 output-polynomial 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 (σ,ρ)-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.