Worst-case time bounds for coloring and satisfiability problems

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

Tomás Feder

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 (6)

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?

This page was built for publication: Worst-case time bounds for coloring and satisfiability problems