CSCE 421/821, Spring 2020, Glossary 6

Assigned: Monday, Feb 24, 2020
Due: Monday, Mar 2, 2020
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:
  1. Bandwidth of a graph
  2. Degree ordering heuristic
  3. Directed acyclic graph
  4. Efficient algorithm
  5. Induced width of an ordering (check your textbook)
  6. Least-domain heuristic
  7. Maximum cardinality heuristic
  8. Min-conflict heuristic
  9. Triangulated graph (a.k.a. chordal graph)
  10. Weighted-degree ordering heuristic (may want to check original paper)
  11. Width of an ordering
  12. Width of a graph
Ordering Algorithms For each of the following algorithms, please explain: (1) The goal of the algorithm and (2) How it operates (informally and in words):
  1. Max Cardinality ordering algorithm (Dechter Fig 4.3)
  2. Min-Fill algorithm (Dechter Fig 4.4)
  3. Width algorithm of Freuder (Dechter 4.2)
Do not forget to list your references.
Berthe Y. Choueiry