Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width
Copyright policy )Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width
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.
- French National Centre for Scientific Research France
- University of Bergen Norway
- Clermont Université France
- Université de Lorraine (UL) France
- University of Lorraine France
FOS: Computer and information sciences, local linear MIM-width, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Enumeration in graph theory, output-polynomial enumeration, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Graph algorithms (graph-theoretic aspects), linear delay, Computer Science - Data Structures and Algorithms, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Data Structures and Algorithms (cs.DS), domination problem
FOS: Computer and information sciences, local linear MIM-width, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Enumeration in graph theory, output-polynomial enumeration, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Graph algorithms (graph-theoretic aspects), linear delay, Computer Science - Data Structures and Algorithms, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Data Structures and Algorithms (cs.DS), domination problem
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).15 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!