An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
From MaRDI portal
Publication:494806
DOI10.1007/s00453-014-9875-7zbMath1330.05118OpenAlexW2041588579MaRDI QIDQ494806
Yngve Villanger, Dieter Kratsch, Pinar Heggernes, Petr A. Golovach
Publication date: 2 September 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-014-9875-7
Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Transversal (matching) theory (05D15) 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 (15)
Enumeration of Maximal Irredundant Sets for Claw-Free Graphs ⋮ Enumeration of maximal irredundant sets for claw-free graphs ⋮ Proximity Search for Maximal Subgraph Enumeration ⋮ Extension of some edge graph problems: standard, parameterized and approximation complexity ⋮ Invited talks ⋮ Output-polynomial enumeration on graphs of bounded (local) linear MIM-width ⋮ Enumerating Minimal Transversals of Hypergraphs without Small Holes ⋮ Efficient enumeration of dominating sets for sparse graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the dualization in distributive lattices and related problems ⋮ Algorithmic aspects of upper edge domination ⋮ Enumerating Minimal Dominating Sets in Triangle-Free Graphs ⋮ On the complexity of solution extension of optimization problems ⋮ EDGE DOMINATION NUMBER AND THE NUMBER OF MINIMUM EDGE DOMINATING SETS IN PSEUDOFRACTAL SCALE-FREE WEB AND SIERPIŃSKI GASKET
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Some properties of line digraphs
- 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
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs
- On enumerating minimal dicuts and strongly connected subgraphs
- On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs
- Enumeration of Minimal Dominating Sets and Variants
- 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
- A New Algorithm for Generating All the Maximal Independent Sets
- 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
- An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets
- Characterizations of derived graphs
- LATIN 2004: Theoretical Informatics
- Generating all vertices of a polyhedron is hard
This page was built for publication: An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
