graph coloring (optimization version)

GPTKB entity

Statements (27)
Predicate Object
gptkbp:instanceOf theoretical computer science
gptkbp:appliesTo vertices
undirected graphs
gptkbp:approximationAlgorithm greedy coloring
gptkbp:complexity gptkb:NP-hard
gptkbp:estimatedCost yes
gptkbp:exactAlgorithm backtracking
branch and bound
gptkbp:goal minimize number of colors
gptkbp:hasSpecialCase Boolean satisfiability problem
https://www.w3.org/2000/01/rdf-schema#label graph coloring (optimization version)
gptkbp:output chromatic number
gptkbp:parameter chromatic number
gptkbp:prohibits adjacent vertices must have different colors
gptkbp:relatedTo gptkb:k-coloring_problem
graph theory
edge coloring
graph coloring
list coloring
precoloring extension
gptkbp:solutionIs proper coloring
gptkbp:studiedBy gptkb:Francis_Guthrie
gptkbp:usedIn scheduling
register allocation
frequency assignment
gptkbp:bfsParent gptkb:NP-hard_problems
gptkbp:bfsLayer 7