CSCE 421/821, Spring 2009, Glossary 7

Assigned: Monday, March 23, 2009.
Due: Monday, March 30, 2009.
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.

Search your textbook, notes, the web, or the library to define/describe the following. It is very important to list all your references.

  1. Binary or 2-way branching (in a search tree)
  2. Bipartite Graph
    1. Definition of a Bipartite Graph
    2. A maximal matching in a bipartite graph
    3. A free edge in a matching in a bipartite graph
    4. A free vertex in a matching in a bipartite graph
    5. A vital edge in a bipartite graph
  3. Box Consistency (for continuous domains CSPs)
  4. Generalized Arc Consistency
  5. k-way branching (in a search tree)
  6. MAX-CSP
  7. Neighborhood inverse consistency
  8. Relational Arc Consistency
  9. Relational Path Consistency
  10. Singleton Arc Consistency
  11. Simple path in a graph (updated)
  12. Strongly connected component in a directed graph
  13. Value graph of an all-diff contraint
  14. Weighted CSP

Berthe Y. Choueiry