An improved exact algorithm for minimum dominating set in chordal graphs

DOI10.1016/j.ipl.2021.106206OpenAlexW3199257895MaRDI QIDQ2059888

Faisal N. Abu-Khzam

Publication date: 14 December 2021

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2021.106206

zbMATH Keywords

graph algorithmschordal graphsexact algorithmsminimum dominating set\(t\)-semi-simplicial vertex

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Bounds for the connected domination number of maximal outerplanar graphs

Cites Work

• Unnamed Item
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
• An exact algorithm for connected red-blue dominating set
• Enumerating minimal dominating sets in chordal graphs
• On rigid circuit graphs
• Enumeration of minimal connected dominating sets for chordal graphs
• Domination chain: characterisation, classical complexity, parameterised complexity and approximability
• Enumeration and maximum number of minimal dominating sets for chordal graphs
• A Faster Algorithm for Dominating Set Analyzed by the Potential Method
• Dominating Sets in Chordal Graphs
• Enumeration and maximum number of maximal irredundant sets for chordal graphs

This page was built for publication: An improved exact algorithm for minimum dominating set in chordal graphs