Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6876077 | Theoretical Computer Science | 2015 | 15 Pages |
Abstract
A spanning tree of an unweighted graph is a minimum average stretch spanning tree if it minimizes the ratio of sum of the distances in the tree between the end vertices of the graph edges and the number of graph edges. For a polygonal 2-tree on n vertices, we present an algorithm to compute a minimum average stretch spanning tree in O(nlogâ¡n) time. This algorithm also finds a minimum fundamental cycle basis in polygonal 2-trees. We show that there is a unique minimum cycle basis in a polygonal 2-tree and it can be computed in linear time.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
N.S. Narayanaswamy, G. Ramakrishna,