Minimum Average Stretch Spanning Trees in 3-Tree Graphs

Minimum average stretch spanning tree (MAST) of an unweighted graph is a spanning tree, which minimizes average tree-distance of endpoints of the edges of the original graph. Solving MAST problem is equivalent to finding minimum fundamental cycle basis (MFCB) of graph. Fundamental cycle basis arises in a variety of application fields, such as electrical circuit testing, generating minimal perfect hash functions, planning cycle timetables, coding of ring compounds and planning complex syntheses in organic chemistry [3]. Minimum stretch spanning trees are used in solving linear systems, approximability of the minimum communication cost spanning tree problem and message-passing model [4]. In this paper, we study minimum average stretch spanning tree in a special type of graphs named nested 3-tree. Nested 3-trees is a subclass of 3-tree graphs and consists of three types. A 3-tree consists of multiple nested 3-trees. First, we determine the value of the minimum average stretch spanning tree and also the tree corresponding to this value in nested 3-tree graph. Finally, we introduce an algorithm that decomposes every 3-tree to three types of nested 3-tree graph.