Structured spanning trees

Abstract

The spanning tree problem in the framework of a hierarchical graph structure, called a structured graph, is considered. A structured graph is a hierarchy of graphs which provides a relational description of an entity at different levels of abstraction. The concept of structured graph is briefly reviewed and some of its properties are presented. The concept of structured spanning tree is defined and its relationship with ‘canonical’ spanning trees is investigated. An algorithm is presented for computing a structured spanning tree of a graph from its canonical spanning tree. An algorithm for finding a minimum-cost canonical spanning tree of a graph by operating on its structured graph representation is developed. The study of structured spanning trees is motivated by their application to hierarchical design and processing of VLSI circuits and communication networks.

Publication
The Computer Journal