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
polynomial time algorithm; linear time algorithm; dominating induced matching; chordal bipartite graphs; efficient edge domination; hole-free graphs; weakly chordal graphs
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