On the enumeration and counting of minimal dominating sets in interval and permutation graphs

DOI10.1007/978-3-642-45030-3_32MaRDI QIDQ2872098zbMATH OpenOpenAlexFDO

Authors Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary, Lhouari Nourine, Takeaki Uno

Publication date 14 January 2014

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-45030-3_32

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)

Recommendations

• Minimal dominating sets in interval graphs and trees
• Counting minimal dominating sets
• Enumeration of minimal dominating sets and variants
• On the enumeration of minimal dominating sets and related notions
• Dominating Set Counting in Graph Classes

Cited in

(17)

• Locally definable vertex set properties are efficiently enumerable
• Enumerating Minimal Dominating Sets in Triangle-Free Graphs
• On the number of minimal dominating sets on some graph classes
• Enumeration of maximal irredundant sets for claw-free graphs
• Enumeration of maximal irredundant sets for claw-free graphs
• Enumerating minimal dominating sets in chordal bipartite graphs
• Minimal dominating sets in interval graphs and trees
• A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs
• Finding minimum dominating cycles in permutation graphs
• An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
• Counting minimal transversals of -acyclic hypergraphs
• Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
• Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
• Enumeration of minimal dominating sets and variants
• Distributed interactive proofs for the recognition of some geometric intersection graph classes
• Counting minimal dominating sets
• Polynomial delay algorithm for listing minimal edge dominating sets in graphs

This page was built for publication: On the enumeration and counting of minimal dominating sets in interval and permutation graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2872098)