Construction of natural cycletrees

Margus Veanes and Jonas Barklund

Abstract

In this article, the following question is answered: Given a cycle C, of size N, how can one compute, in O(N) time, a minimal set of edges E such that adjoining E to the cycle yields a graph with a binary spanning tree having minimal total path length? The answer is given through an algorithm for top-down construction of natural cycletrees, where the structure of each subtree is restricted by a split relation between certain properties of the subtree.

Details

Publication typeArticle
Published inInformation Processing Letters
URLhttp://dx.doi.org/10.1016/S0020-0190(96)00179-2
Pages313-318
Volume60
PublisherElsevier
> Publications > Construction of natural cycletrees