Dominating set based exact algorithms for \(3\)-coloring
type: Item
instance of: scholarly article
title: Dominating set based exact algorithms for \(3\)-coloring
zbMATH Open document ID: 1259.05171
author: N. S. Narayanaswamy
author: C. R. Subramanian
published in: Information Processing Letters
publication date: 2013-04-04T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6150264
zbMATH Keywords: graph algorithms
zbMATH Keywords: design of algorithms
zbMATH Keywords: graph coloring
zbMATH Keywords: \(3\)-coloring
zbMATH Keywords: exact algorithms
zbMATH Keywords: exponential time algorithms
MaRDI profile type: Publication
full work available at URL: j.ipl.2010.11.009
OpenAlex ID: W1986075609
cites work: The probabilistic method. With an appendix on the life and work of Paul Erdős.
cites work: Q4252729
cites work: 3-coloring in time
cites work: Q4910710
cites work: Introduction to algorithms
cites work: Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
cites work: The complexity of colouring problems on dense graphs
cites work: Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
cites work: Q4198056
cites work: On the Hardness of 4-Coloring a 3-Colorable Graph
cites work: On the complexity of \(k\)-SAT
cites work: Which problems have strongly exponential complexity?
cites work: A note on the complexity of the chromatic number problem
DOI: 10.1016/J.IPL.2010.11.009
description: scientific article; zbMATH DE number 6150264