Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs

DOI10.1007/978-3-319-21840-3_37zbMath1451.68204arXiv1404.3501OpenAlexW1524268499MaRDI QIDQ3449842

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

Publication date: 30 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1404.3501

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) 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

Enumeration of Maximal Irredundant Sets for Claw-Free Graphs, Enumeration of maximal irredundant sets for claw-free graphs, Minimal dominating sets in interval graphs and trees, Minimal Roman dominating functions: extensions and enumeration, Invited talks, Output-polynomial enumeration on graphs of bounded (local) linear MIM-width, Counting Minimal Dominating Sets, Efficient enumeration of dominating sets for sparse graphs, Unnamed Item, Unnamed Item, Upper Domination: Complexity and Approximation, A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs, Enumeration and maximum number of minimal dominating sets for chordal graphs, On the complexity of solution extension of optimization problems, Extension and its price for the connected vertex cover problem

Cites Work

• Unnamed Item
• Unnamed Item
• Enumerating minimal subset feedback vertex sets
• Rigorous and accurate enclosure of invariant manifolds on surfaces
• A new polynomial-time algorithm for linear programming
• Generating cut conjunctions in graphs and related problems
• On enumerating all minimal solutions of feedback problems
• Reverse search for enumeration
• Efficient algorithms for dualizing large-scale hypergraphs
• On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs
• An Efficient Algorithm for the Transversal Hypergraph Generation
• Enumeration of the Monomials of a Polynomial and Related Complexity Classes
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
• 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
• On the Enumeration of Minimal Dominating Sets and Related Notions
• Algorithm Theory - SWAT 2004
• An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets