A linear-time algorithm for paired-domination problem in strongly chordal graphs

作者：Chen Lei; Lu Changhong^*; Zeng Zhenbing

来源：Information Processing Letters, 2009, 110(1): 20-23.

DOI：10.1016/j.ipl.2009.09.014

• Algorithms
• Combinatorial problems
• Paired-domination
• Domination
• Strongly chordal graph
• Chordal graph

Let G = (V, E) be a simple graph without isolated vertices. A vertex set S subset of V is a paired-dominating set if every vertex in V - S has at least one neighbor in S and the induced subgraph G vertical bar S vertical bar has a perfect matching. In this paper, we present a linear-time algorithm to find a minimum paired-dominating set in strongly chordal graphs if the strong (elimination) ordering of the graph is given in advance.

• 出版日期2009-12-1
• 单位华东师范大学