文章基本信息

标题：3-Coloring in time O(1.3446^n): a no-MIS algorithm
本地全文：下载
作者：Richard Beigel ; David Eppstein
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1995
卷号：1995
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We consider worst case time bounds for NP-complete problems including 3-SAT, 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 [R. Floyd & R. Beigel, The Language of Machines]. 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.
关键词：3-color, 3-SAT, algorithm, coloring, edge-color, graph coloring, list-color, NP-complete, SSS, symbol system, worst-case