DRAFT FOR SUBMISSION - 9-17-96

Constraints 1 1 October 1996

Stephen Beale Exploiting Graph Topology...

Stephen Beale sb@crl.nmsu.edu Computing Research Laboratory, New Mexico State University, Las Cruces, New Mexico, 88003
Carnegie Mellon University, Pittsburgh, PA 15217

Abstract:

Constraint satisfaction problems can be modeled as graphs with the decision points represented as vertices and constraints drawn as edges. Graphs can be one-dimensional (trees), two-dimensional (planes), three-dimensional (cubes), etc., up to N-dimensional (cliques), or combinations of any of these. Using graph decomposition methods along with a novel approach to solution synthesis and branch-and-bound, we are able to reduce problem dimensionality in such a way that tree-shaped constraint graphs can be processed in linear time, with optimal results guaranteed, and higher-dimensional inputs can have their complexity significantly reduced. In this paper, we present the key concepts and algorithms behind this approach and apply the results to graph coloring and natural language semantic analysis. We also introduce a new measure of complexity, discuss its relationship to graph topology and show how it can be measured for specific problems.

Solution Synthesis, Constraint Satisfaction, Branch-and-Bound, Graph Coloring, Natural Language Processing

• Introduction
• Constraint Satisfaction and Solution Synthesis Methods
• Solution Synthesis Overview
• Optimization-Driven Solution Synthesis
• Graph Coloring
• Subgraph Construction
• Graph Topology
• An Example from Natural Language Processing
  • Constraint Satisfaction Hunters in Computational Semantics
  • Using Branch-and-Bound in an Uncertain World
    • Branch-and-Bound Results
• Conclusion
• About this document ...