论文部分内容阅读
最小独立支配集问题是图论中经典的NP完全问题之一，要求在给定的图中找到一组顶点D，D的顶点互不相邻（独立），且D之外的每个顶点都有相邻的顶点包含于D（支配）。最小独立支配集问题在很多领域中被广泛应用，包括编码理论、密码学、图像处理、数值分析等。 已知在图的特殊子类中，最小独立支配集问题的计算复杂度存在变化。在普通二部图中问题仍是NP完全的，而在二部图的特殊子类:凸二部图中，求解问题有多项式时间算法。树凸二部图是最近提出的一种受限制的二部图，是普通二部图的子类、凸二部图的超类。它的其中一部可以排列为树，使得另一部中每个顶点的邻域都在树中相邻。本文主要研究最小独立支配集问题在树凸二部图上复杂度，通过对星凸二部图、三岔树凸二部图等特殊树凸二部图的探索和分析，发现了计算复杂度从NP变化为P的关键指标:树凸二部图的凸树中度数大于2的顶点的度数之和。上述指标是否常数有界决定了最小独立支配集问题是否多项式时间可解。