Structured spanning trees

M. Ancona, L. De Floriani, J. S. Deogun

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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 tree 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.

Original languageEnglish (US)
Pages (from-to)344-355
Number of pages12
JournalComputer Journal
Issue number4
StatePublished - 1990
Externally publishedYes

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Structured spanning trees'. Together they form a unique fingerprint.

Cite this