Worst-case time bounds for coloring and satisfiability problems

DOI10.1016/S0196-6774(02)00224-9zbMath1051.68076MaRDI QIDQ4806606

Tomás Feder, Rajeev Motwani

Publication date: 14 May 2003

Published in: Journal of Algorithms (Search for Journal in Brave)

zbMATH Keywords

NP-complete problems\(k\)-colorability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

The Time Complexity of Constraint Satisfaction, Exact algorithms for exact satisfiability and number of perfect matchings, Complexity analysis of a decentralised graph colouring algorithm, Faster graph coloring in polynomial space, Locally consistent constraint satisfaction problems, Which problems have strongly exponential complexity?