An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
From MaRDI portal
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) Graph operations (line graphs, products, etc.) (05C76) Transversal (matching) theory (05D15)
Recommendations
- An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
- Polynomial delay algorithm for listing minimal edge dominating sets in graphs
- Enumerating minimal dominating sets in chordal bipartite graphs
- A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs
- Enumeration of minimal dominating sets and variants
Cites work
- scientific article; zbMATH DE number 3675952 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 1931696 (Why is no real title available?)
- scientific article; zbMATH DE number 3102314 (Why is no real title available?)
- A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions
- A New Algorithm for Generating All the Maximal Independent Sets
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- An Algorithm to Enumerate All Cutsets of a Graph in Linear Time per Cutset
- An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
- Characterizations of derived graphs
- Dual subimplicants of positive Boolean functions
- Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
- Enumeration of minimal dominating sets and variants
- Enumeration of the Elementary Circuits of a Directed Graph
- Exact transversal hypergraphs and application to Boolean \(\mu\)-functions
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- Generating all vertices of a polyhedron is hard
- Generating cut conjunctions in graphs and related problems
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- LATIN 2004: Theoretical Informatics
- Linear delay enumeration and monadic second-order logic
- NP-completeness: a retrospective
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- On enumerating all minimal solutions of feedback problems
- On enumerating minimal dicuts and strongly connected subgraphs
- On generating all maximal independent sets
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs
- On the enumeration and counting of minimal dominating sets in interval and permutation graphs
- On the enumeration of minimal dominating sets and related notions
- On the neighbourhood Helly of some graph classes and applications to the enumeration of minimal dominating sets
- Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs
- Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
- Reverse search for enumeration
- Some properties of line digraphs
- The Maximum Latency and Identification of Positive Boolean Functions
- Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms
Cited in
(19)- Polynomial delay algorithm for listing minimal edge dominating sets in graphs
- Proximity Search for Maximal Subgraph Enumeration
- Algorithmic aspects of upper edge domination
- Enumeration of maximal irredundant sets for claw-free graphs
- Enumerating Minimal Dominating Sets in Triangle-Free Graphs
- An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
- Enumeration of maximal irredundant sets for claw-free graphs
- Extension of some edge graph problems: standard, parameterized and approximation complexity
- On the dualization in distributive lattices and related problems
- Enumerating minimal transversals of hypergraphs without small holes
- scientific article; zbMATH DE number 7650296 (Why is no real title available?)
- Efficient enumeration of dominating sets for sparse graphs
- Edge domination number and the number of minimum edge dominating sets in pseudofractal scale-free web and Sierpiński gasket
- Efficient enumeration of dominating sets for sparse graphs
- On the complexity of solution extension of optimization problems
- Enumerating minimal dominating sets in chordal bipartite graphs
- On kernelization for edge dominating set under structural parameters
- On the neighbourhood Helly of some graph classes and applications to the enumeration of minimal dominating sets
- Invited talks
This page was built for publication: An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494806)
