An asteroidal triple is a set of three vertices such that there is a path between any pair of them avoiding the closed neighborhood of the third. A graph is called AT-free if it does not have an asteroidal triple. We show that there is an O(n~2 (m-bar+1)) time algorithm to compute the maximum cardinality of an independent set for AT-free graphs, where n is the number of vertices and m-bar is the number of non edges of the input graph. Furthermore we obtain O(n~2 (m-bar+1)) time algorithms to solve the INDEPENDENT DOMINATING SET and the INDEPENDENT PERFECT DOMINATING SET problem on AT-free graphs. We also show how to adapt these algorithms such that they solve the corresponding problem for graphs with bounded asteroidal number in polynomial time. Finally we observe that the problems CLIQUE and PARTITION INTO CLIQUES remain NP-complete when restricted to AT-free graphs.
展开▼
机译：小行星三元组是一组三个顶点，这样它们之间就存在一条路径，可以避免第三个顶点的封闭邻域。如果图形没有小行星三元组，则称为无AT。我们证明了有一种O（n〜2（m-bar + 1））时间算法可以为无AT图计算独立集的最大基数，其中n是顶点数，m-bar是数输入图的非边缘数。此外，我们获得了O（n〜2（m-bar + 1））时间算法来解决无AT图上的独立占优集和独立占优集问题。我们还展示了如何调整这些算法，以便它们解决多项式时间内有界小行星数的图的相应问题。最后，我们观察到，仅限于无AT的图时，CLIQUE和PARTITION INTO CLIQUES问题仍然是NP-complete。
展开▼
