Accession Number:

ADA099221

Title:

Implementation and Evaluation of a Graph Partitioning Technique Based on a High-Density Clustering Model.

Descriptive Note:

Technical rept.,

Corporate Author:

ALFRED P SLOAN SCHOOL OF MANAGEMENT CAMBRIDGE MA CENTER FOR INFORMATION SYSTEMS RESEARCH

Personal Author(s):

Report Date:

1981-02-01

Pagination or Media Count:

68.0

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

Subject Categories:

  • Theoretical Mathematics
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE