On the Neighbourhood Helly of Some Graph Classes and Applications to the Enumeration of Minimal Dominating Sets

DOI10.1007/978-3-642-35261-4_32zbMath1260.05163OpenAlexW167097032MaRDI QIDQ4909546

Lhouari Nourine, Vincent Limouzy, Mamadou Moustapha Kanté, Arnaud Mary

Publication date: 21 March 2013

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

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

zbMATH Keywords

algorithmsenumerationline graphspath graphsbounded neighbourhood Hellyminimal domonating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Related Items (16)

Enumeration of Maximal Irredundant Sets for Claw-Free Graphs ⋮ Enumeration of maximal irredundant sets for claw-free graphs ⋮ Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs ⋮ Minimal dominating sets in interval graphs and trees ⋮ Minimal dominating sets in graph classes: combinatorial bounds and enumeration ⋮ Extension of some edge graph problems: standard, parameterized and approximation complexity ⋮ Enumerating minimal dominating sets in chordal bipartite graphs ⋮ Output-polynomial enumeration on graphs of bounded (local) linear MIM-width ⋮ On the number of minimal dominating sets on some graph classes ⋮ An incremental polynomial time algorithm to enumerate all minimal edge dominating sets ⋮ Efficient enumeration of dominating sets for sparse graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the dualization in distributive lattices and related problems ⋮ Enumerating Minimal Dominating Sets in Triangle-Free Graphs ⋮ A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs

This page was built for publication: On the Neighbourhood Helly of Some Graph Classes and Applications to the Enumeration of Minimal Dominating Sets