Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs

DOI10.1007/978-3-642-35261-4_30zbMath1260.05108arXiv1207.0953OpenAlexW1950090232MaRDI QIDQ4909544

Arne Leitert, Andreas Brandstädt, Dieter Rautenbach

Publication date: 21 March 2013

Published in: Algorithms and Computation (Search for Journal in Brave)

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

zbMATH Keywords

graphshypergraphspolynomial time algorithmsefficient dominating setefficient dominationefficient edge dominationefficient edge dominating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (24)

Perfect edge domination: hard and solvable cases ⋮ Kernelization of edge perfect code and its variants ⋮ Efficient and perfect domination on circular-arc graphs ⋮ Modelling and solving the perfect edge domination problem ⋮ Graph classes with and without powers of bounded clique-width ⋮ On Strong Tree-Breadth ⋮ A note on efficient domination in a superclass of \(P_5\)-free 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 ⋮ 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 ⋮ Fast algorithms for some dominating induced matching problems ⋮ Efficient domination for classes of \(P_6\)-free graphs ⋮ Dominating induced matching in some subclasses of bipartite graphs ⋮ Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications ⋮ Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs ⋮ On efficient domination for some classes of \(H\)-free chordal graphs ⋮ On efficient domination for some classes of \(H\)-free chordal graphs ⋮ Efficient Domination for Some Subclasses of $$P_6$$ -free Graphs in Polynomial Time ⋮ The Maximum Number of Dominating Induced Matchings ⋮ A Survey of the Game “Lights Out!” ⋮ Efficient \((j, k)\)-dominating functions ⋮ Exact algorithms for dominating induced matching based on graph partition

This page was built for publication: Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs