Exact algorithms for edge domination

DOI10.1007/s00453-011-9546-xzbMath1264.68211WikidataQ59567537 ScholiaQ59567537MaRDI QIDQ1945174

Hans L. Bodlaender, Johan M. M. van Rooij

Publication date: 3 April 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9546-x

zbMATH Keywords

exact algorithms; edge dominating set; exponential time algorithms; measure and conquer; minimum maximal matching

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

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.)