On claw-free asteroidal triple-free graphs
On claw-free asteroidal triple-free graphs
复制标题
关于无爪小行星三自由图
DOI：
10.1016/s0166-218x(01)00208-6
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
D. Kratsch
中科院分区：
文献类型：
--
作者：
Harald Hempel;D. Kratsch
我们提出了一种用于识别无爪 AT-free 图的 O(n2.376) 算法，以及一种用于计算无爪 AT-free 图的所有中心顶点集的线性时间算法。此外，我们还给出了解决独立集、支配集和着色问题的有效算法。我们认为，除非找到针对许多著名图形问题（例如三角形识别和二分匹配）的更好算法，否则实现的所有运行时间都是最佳的。我们的算法利用了无爪 AT 无图的 2LexBFS 方案的结构。
We present an O(n2.376) algorithm for recognizing claw-free AT-free graphs and a linear-time algorithm for computing the set of all central vertices of a claw-free AT-free graph. In addition, we give efficient algorithms that solve the problems INDEPENDENT SET, DOMINATING SET, and COLORING. We argue that all running times achieved are optimal unless better algorithms for a number of famous graph problems such as triangle recognition and bipartite matching have been found. Our algorithms exploit the structure of 2LexBFS schemes of claw-free AT-free graphs.