3-coloring in time 0(1.3446/sup n/): a no-MIS algorithm
3-coloring in time 0(1.3446/sup n/): a no-MIS algorithm
复制标题
时间 0 中的 3 色着色（1.3446/sup n/）：无 MIS 算法
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
D. Eppstein
中科院分区：
文献类型：
--
作者：
R. Beigel;D. Eppstein
我们考虑NP完全问题（包括3 - 着色、3 - 边着色和3 - 列表着色）的最坏情况时间界限。我们的算法基于这些问题的一种通用推广，称为符号系统可满足性，简称为SSS。3 - SAT等价于(2, 3)-SSS，而上述其他问题是(3, 2)-SSS的特殊情况；从(a, b)-SSS到(b, a)-SSS还存在一种自然的对偶变换。我们给出了一个针对(3, 2)-SSS的快速算法，并利用它来改进解决上述其他问题的时间界限。
We consider worst case time bounds for NP-complete problems including 3-coloring, 3-edge-coloring, and 3-list-coloring. Our algorithms are based on a common generalization of these problems, called symbol-system satisfiability or, briefly, SSS. 3-SAT is equivalent to (2,3)-SSS while the other problems above are special cases of (3,2)-SSS; there is also a natural duality transformation from (a,b)-SSS to (b,a)-SSS. We give a fast algorithm for (3,2)-SSS and use it to improve the time bounds for solving the other problems listed above.