Efficient dominating and edge dominating sets for graphs and hypergraphs
From MaRDI portal
efficient dominating setefficient dominationefficient edge dominating setefficient edge dominationgraphshypergraphspolynomial time algorithms
Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)
Abstract: Let G=(V,E) be a graph. A vertex dominates itself and all its neighbors, i.e., every vertex v in V dominates its closed neighborhood N[v]. A vertex set D in G is an efficient dominating (e.d.) set for G if for every vertex v in V, there is exactly one d in D dominating v. An edge set M is an efficient edge dominating (e.e.d.) set for G if it is an efficient dominating set in the line graph L(G) of G. The ED problem (EED problem, respectively) asks for the existence of an e.d. set (e.e.d. set, respectively) in the given graph. We give a unified framework for investigating the complexity of these problems on various classes of graphs. In particular, we solve some open problems and give linear time algorithms for ED and EED on dually chordal graphs. We extend the two problems to hypergraphs and show that ED remains NP-complete on alpha-acyclic hypergraphs, and is solvable in polynomial time on hypertrees, while EED is polynomial on alpha-acyclic hypergraphs and NP-complete on hypertrees.
Recommendations
Cited in
(33)- Efficient edge domination in regular graphs
- Efficient edge domination problems in graphs
- Perfect edge domination: hard and solvable cases
- Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications
- Weighted efficient domination for some classes of H-free and of (H₁, H₂)-free graphs
- Fast algorithms for some dominating induced matching problems
- Efficient domination for classes of \(P_6\)-free graphs
- Efficient \((j, k)\)-dominating functions
- Modelling and solving the perfect edge domination problem
- Exact algorithms for dominating induced matching based on graph partition
- A note on efficient domination in a superclass of \(P_5\)-free graphs
- Efficient domination and efficient edge domination: a brief survey
- Efficient domination for some subclasses of P₆-free graphs in polynomial time
- A Survey of the Game “Lights Out!”
- On strong tree-breadth
- Kernelization of edge perfect code and its variants
- Efficient and perfect domination on circular-arc graphs
- Dominating induced matchings for \(P_7\)-free graphs in linear time
- Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
- The Maximum Number of Dominating Induced Matchings
- Combinatorial and spectral properties of König-Egerváry graphs
- Exact algorithms for minimum weighted dominating induced matching
- Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time
- Dominating induced matching in some subclasses of bipartite graphs
- On efficient domination for some classes of \(H\)-free chordal graphs
- On efficient domination for some classes of \(H\)-free chordal graphs
- Perfect codes in m-Cayley hypergraphs
- Diffusion: quiescence and perturbation
- Graphs whose vertices of degree at least 2 lie in a triangle
- Weighted efficient domination for P₈-free bipartite graphs in polynomial time
- A sharp upper bound for the edge dominating number of hypergraphs with minimum degree
- A study on the weighted efficient domination problem for C₄-free bipartite graphs
- Graph classes with and without powers of bounded clique-width
This page was built for publication: Efficient dominating and edge dominating sets for graphs and hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4909544)
