Clustering a DAG for CAD databases

A DAG (direct acyclic graph) is an important data structure which requires efficient support in CAD (computer-aided design) databases. It typically arise from the design hierarchy, which describes complex designs in terms of subdesigns. A study is made of the properties of the three types of cluster...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on software engineering 1988-11, Vol.14 (11), p.1684-1699
Main Authors: Banerjee, J., Kim, W., Kim, S.-J., Garza, J.F.
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Applied sciences
Assembly systems
CAD
Clustering algorithms
Clusters
Computer aided design
Computer science
control theory
systems
Data structures
Design
Design automation
Design engineering
Designers
Exact sciences and technology
Graphs
Information retrieval
Information systems. Data bases
Memory organisation. Data processing
Methods
Microprocessor chips
Sequence
Software
Software systems
Work stations
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A DAG (direct acyclic graph) is an important data structure which requires efficient support in CAD (computer-aided design) databases. It typically arise from the design hierarchy, which describes complex designs in terms of subdesigns. A study is made of the properties of the three types of clustered sequences of nodes for hierarchies and DAGs, and algorithms are developed for generating the clustered sequences, retrieving the descendants of a given node, and inserting new nodes into existing clustered sequences of nodes which preserve their clustering properties. The performance of the clustering sequences is compared.< >
ISSN:0098-5589
1939-3520
DOI:10.1109/32.9055