版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构:Univ Rostock Inst Inforrnat D-18051 Rostock Germany Univ G DAnnunzio Dipartimento Econ I-65121 Pescara Italy
出 版 物:《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)
年 卷 期:2020年第281卷
页 面:81-95页
核心收录:
学科分类:07[理学] 0701[理学-数学] 070101[理学-基础数学]
主 题:Weighted efficient domination H-free chordal graphs NP-completeness Net-free chordal graphs Extended-gem-free chordal graphs S-1,S-2,S-3-free chordal graphs Polynomial time algorithm Clique-width
摘 要:A vertex set D in a finite undirected graph G is an efficient dominating set (e.d.s for short) of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED) problem, which asks for the existence of an e.d.s. in G, is known to be NP-complete even for very restricted graph classes such as for 2P(3)-free chordal graphs while it is solvable in polynomial time for P-6-free chordal graphs (and even for P-6-free graphs). A standard reduction from the NP-complete Exact Cover problem shows that ED is NP-complete for a very special subclass of chordal graphs generalizing split graphs. The reduction implies that ED is NP-complete e.g. for double-gem-free chordal graphs while it is solvable in linear time for gem-free chordal graphs (by various reasons such as bounded clique-width, distance-hereditary graphs, chordal square etc.), and ED is NP-complete for butterfly-free chordal graphs while it is solvable in linear time for 2P(2)-free graphs. We show that (weighted) ED can be solved in polynomial time for H-free chordal graphs when H is net, extended gem, or S-1,S-2,S-3. (c) 2019 Elsevier B.V. All rights reserved.