A Graph Decomposition Technique Based on a High-Density Clustering Model on Graphs.
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 sub-problems. Functional requirements form a key interface between the users of a system and its designers. In this research effort, a systematic approach has been proposed for the decomposition of the overall set of functional requirements into sub-problems to form a design structure that will exhibit the key characteristics of good design: strong coupling within sub-problems, and weak coupling between them. A scan of the graph decomposition algorithms review that none of the existing techniques is particularly well suited for use in Systematic Design Methodology. In this report, a clustering model on a graph is defined, using the concept of natural or high density clusters which are densely-connected subgraphs separated by relatively few links. A graph decomposition techniques based on this high-density clustering model is developed for identifying the best natural partition for a given graph.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1980
- Accession Number
- ADA090348
Entities
People
- M. Anthony Wong