This item is non-discoverable
Loading...
Non-discoverable
3-coloring in time script O sign(1.3289<sup>n</sup>)
Beigel, R Eppstein, D
Beigel, R
Eppstein, D
Citations
Altmetric:
Genre
Pre-print
Date
2005-02-01
Advisor
Committee member
Group
Department
Permanent link to this record
Collections
Research Projects
Organizational Units
Journal Issue
DOI
10.1016/j.jalgor.2004.06.008
Abstract
We consider worst case time bounds for several NP-complete problems, based on a constraint satisfaction (CSP) formulation of these problems: (a,b)-CSP instances consist of a set of variables, each with up to a possible values, and constraints disallowing certain b-tuples of variable values; a problem is solved by assigning values to all variables satisfying all constraints, or by showing that no such assignment exist. 3-SAT is equivalent to (2,3)-CSP while 3-coloring and various related problems are special cases of (3,2)-CSP; there is also a natural duality transformation from (a,b)-CSP to (b,a)-CSP. We show that n-variable (3,2)-CSP instances can be solved in time O(1.3645n), that satisfying assignments to (d,2)-CSP instances can be found in randomized expected time O((0.4518d)n); that 3-coloring of n-vertex graphs can be solved in time O(1.3289n); that 3-list-coloring of n-vertex graphs can be solved in time O(1.3645n); that 3-edge-coloring of n-vertex graphs can be solved in time O(2n/2), and that 3-satisfiability of a formula with t 3-clauses can be solved in time O(nO(1)+1.3645t). © 2004 Elsevier Inc. All rights reserved.
Description
Citation
Citation to related work
Elsevier BV
Has part
Journal of Algorithms
ADA compliance
For Americans with Disabilities Act (ADA) accommodation, including help with reading this content, please contact scholarshare@temple.edu