Efficient Edge Domination on Hole-Free Graphs in Polynomial Time

DOI10.1007/978-3-642-12200-2_56zbMath1283.05197MaRDI QIDQ3557057

Andreas Brandstädt, Ragnar Nevries, Christian Hundt

Publication date: 27 April 2010

Published in: LATIN 2010: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-12200-2_56

zbMATH Keywords

polynomial time algorithm; linear time algorithm; dominating induced matching; chordal bipartite graphs; efficient edge domination; hole-free graphs; weakly chordal graphs

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

The Maximum Number of Dominating Induced Matchings, Hereditary Efficiently Dominatable Graphs, Dominating induced matching in some subclasses of bipartite graphs, Finding dominating induced matchings in \(P_{10}\)-free graphs in polynomial time, Efficient domination through eigenvalues, Kernelization of edge perfect code and its variants, 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, Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time, On the dominating induced matching problem: spectral results and sharp bounds, Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs, Fast algorithms for some dominating induced matching problems, Efficient domination for classes of \(P_6\)-free graphs, Finding dominating induced matchings in \(P_9\)-free graphs in polynomial time, Dominating induced matchings in \(S_{1 , 2 , 4}\)-free graphs, Modelling and solving the perfect edge domination problem, Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time, Exact algorithms for dominating induced matching based on graph partition, Dominating induced matchings in graphs without a skew star