Efficient Edge Domination on Hole-Free Graphs in Polynomial Time

DOI10.1007/978-3-642-12200-2_56zbMath1283.05197OpenAlexW1546403474MaRDI 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 algorithmlinear time algorithmdominating induced matchingchordal bipartite graphsefficient edge dominationhole-free graphsweakly chordal graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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 (22)

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

This page was built for publication: Efficient Edge Domination on Hole-Free Graphs in Polynomial Time