咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >Polar graphs and maximal indep... 收藏

Polar graphs and maximal independent sets

极的图和最大的独立集合

作     者:Lozin, Vadim V. Mosca, Raffaele 

作者机构:Rutgers State Univ RUTCOR Piscataway NJ 08854 USA Univ Studi GD Annunzio Dipartimento Sci I-65127 Pescara Italy 

出 版 物:《DISCRETE MATHEMATICS》 (离散数学)

年 卷 期:2006年第306卷第22期

页      面:2901-2908页

核心收录:

学科分类:07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主  题:maximal independent set polynomial-time algorithm 

摘      要:We study two central problems of algorithmic graph theory: finding maximum and minimum maximal independent sets. Both problems are known to be NP-hard in general. Moreover, they remain NP-hard in many special classes of graphs. For instance, the problem of finding minimum maximal independent sets has been recently proven to be NP-hard in the class of so-called (1, 2)-polar graphs. On the other hand, both problems can be solved in polynomial time for (1, I)-polar, also known as split graphs. In this paper, we address the question of distinguishing new classes of graphs admitting polynomial-time solutions for the two problems in question. To this end, we extend the hierarchy of (alpha, beta)-polar graphs and study the computational complexity of the problems on polar graphs of special types. (c) 2006 Elsevier B.V. All rights reserved.

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

用户名:未登录
我的评分