Article ID Journal Published Year Pages File Type
5777226 Electronic Notes in Discrete Mathematics 2016 4 Pages PDF
Abstract
A minimum average stretch spanning tree of a graph is a spanning tree that minimizes the average stretch. We present a necessary-and-sufficient condition for a spanning tree to be a minimum average stretch spanning tree (mast) in grid graphs and provide a linear-time algorithm to construct an mast.
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
On Minimum Average Stretch Spanning Trees in Grid Graphs
Authors
, ,