An O *(1.1939 n ) Time Algorithm for Minimum Weighted Dominating Induced Matching

DOI10.1007/978-3-642-45030-3_52zbMath1407.05223arXiv1303.0035OpenAlexW2962927326MaRDI QIDQ2872119

Min Chih Lin, Michel J. Mizrahi, Jayme Luiz Szwarcfiter

Publication date: 14 January 2014

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

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

zbMATH Keywords

exact algorithmsdominating induced matchingsbranch\&reduce

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (7)

Perfect edge domination: hard and solvable cases ⋮ Kernelization of edge perfect code and its variants ⋮ Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs ⋮ Exact algorithms for minimum weighted dominating induced matching ⋮ Fast algorithms for some dominating induced matching problems ⋮ The Maximum Number of Dominating Induced Matchings ⋮ Exact algorithms for dominating induced matching based on graph partition

This page was built for publication: An O *(1.1939 n ) Time Algorithm for Minimum Weighted Dominating Induced Matching