Enumerating minimal dominating sets in chordal bipartite graphs
From MaRDI portal
Publication:896653
DOI10.1016/j.dam.2014.12.010zbMath1326.05105OpenAlexW2084621880MaRDI QIDQ896653
Petr A. Golovach, Pinar Heggernes, Yngve Villanger, Dieter Kratsch, Mamadou Moustapha Kanté
Publication date: 10 December 2015
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2014.12.010
Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (13)
Enumeration of Maximal Irredundant Sets for Claw-Free Graphs ⋮ Enumeration of maximal irredundant sets for claw-free graphs ⋮ On strictly chordality-\(k\) graphs ⋮ Minimal Roman dominating functions: extensions and enumeration ⋮ Invited talks ⋮ Output-polynomial enumeration on graphs of bounded (local) linear MIM-width ⋮ Efficient enumeration of dominating sets for sparse graphs ⋮ 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 ⋮ On the complexity of solution extension of optimization problems ⋮ Linear algorithms for red and blue domination in convex bipartite graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph
- Generating cut conjunctions in graphs and related problems
- Linear delay enumeration and monadic second-order logic
- On generating all maximal independent sets
- Exact transversal hypergraphs and application to Boolean \(\mu\)-functions
- On enumerating all minimal solutions of feedback problems
- Reverse search for enumeration
- Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
- On enumerating minimal dicuts and strongly connected subgraphs
- On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs
- Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms
- Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- An Algorithm to Enumerate All Cutsets of a Graph in Linear Time per Cutset
- Perfect Elimination and Chordal Bipartite Graphs
- Graph Classes: A Survey
- Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
- The Maximum Latency and Identification of Positive Boolean Functions
- A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions
- NP-completeness: A retrospective
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- On the Neighbourhood Helly of Some Graph Classes and Applications to the Enumeration of Minimal Dominating Sets
- Dual subimplicants of positive Boolean functions
- Enumeration of the Elementary Circuits of a Directed Graph
- On the Enumeration of Minimal Dominating Sets and Related Notions
- LATIN 2004: Theoretical Informatics
- Generating all vertices of a polyhedron is hard
This page was built for publication: Enumerating minimal dominating sets in chordal bipartite graphs
