咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >On efficient domination for so... 收藏

On efficient domination for some classes of H-free chordal graphs

在为 H 免费的索的图的一些班的有效支配上

作     者:Brandstadt, Andreas Mosca, Raffaele 

作者机构: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[理学-基础数学] 

基  金:We gratefully thank the anonymous reviewers for their comments and corrections. The second author would like to witness that he just tries to pray a lot and is not able to do anything without that - ad laudem Domini 

主  题: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.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分