2015/09/12 by Petr A. Golovach, Golovach, Petr A., Pinar Heggernes +9 · 1 citation
Computer Science · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #Error Correcting Code Techniques #FOS: Computer and information sciences #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1509.03753
openalex publication_date 2015/09/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The linear induced matching width (LMIM-width) of a graph is a width\nparameter defined by using the notion of branch-decompositions of a set\nfunction on ternary trees. In this paper we study output-polynomial enumeration\nalgorithms on graphs of bounded LMIM-width and graphs of bounded local\nLMIM-width. In particular, we show that all 1-minimal and all 1-maximal\n(\σ,\ρ)-dominating sets, and hence all minimal dominating sets, of graphs\nof bounded LMIM-width can be enumerated with polynomial (linear) delay using\npolynomial space. Furthermore, we show that all minimal dominating sets of a\nunit square graph can be enumerated in incremental polynomial time.\n