CSCE 421/821, Fall 2014, Glossary 5
Assigned: Friday, Oct 17
Due: Friday, Oct 24
Note: Glossaries are optional but they allow you improve
your grade. Also, you are responsible for knowing the exact
definition of the terms in a glossary at any point in time, including
during a quiz.
You may need to check the following documents:
 Bandwidth of a graph
 Complete graph

Constraint density of a binary CSP

Constraint tightness of a binary constraint
 Clique
 Degree ordering heuristic
 Directed acyclic graph
 Efficient algorithm
 Failfirst principle
 Induced width of an ordering (check your textbook)
 Leastdomain heuristic
 Mathematical Programming
 Maintaining arcconsistency (MAC)
 Maximal cliques in a graph
 Maximum cardinality heuristic
 Minconflict heuristic
 Phase transition
 Critical value of order parameter
 Order parameter
 Phase transition
 Tractable problem
 Triangulated graph (a.k.a. chordal graph)
 Weighteddegree ordering heuristic (may want to check original paper)
 Width of an ordering
 Width of a graph
Do not forget to list your references.
Berthe Y. Choueiry