Implementation and Evaluation of a Graph Partitioning Technique Based on a High-Density Clustering Model.
Abstract
Complex design problems are characterized by a multitude of competing requirements. System designers frequently find the scope of the problem beyond their conceptual abilities, and attempt to cope with this difficulty by decomposing the original design problem into smaller, more manageable subproblems. In the SDM research effort, a systematic approach has been proposed for the decomposition of the set of functional requirements of a design problem into subsets (called subproblems) to form a design structure that will exhibit key characteristics of good design: strong coupling among requirements within subproblems and weak coupling between subproblems. This report documents the implementation of an efficient graph partitioning technique based on a high-density clustering model. The new method identifies the 'high-density regions' in the graph, which are sets of functional requirements exhibiting a relatively high degree of interdependency, and associates them with the different subsets of the design problem. The new technique, as currently implemented, is applied to several problems from the design literature. The results indicate that the proposed approach gives solutions that are conceptually and intuitively appealing, and that these partitions are consistent with the currently accepted decomposition. Although direct comparison with computational requirements of other partitioning procedures is difficult due to different machine implementations, the empirical evidence suggest that the new method is useful for decomposing design problems too large for the procedures currently in use. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1981
- Accession Number
- ADA099221
Entities
People
- James M. Lattin