On minimum average stretch spanning trees in polygonal 2-trees

DOI10.1007/978-3-319-04657-0_29MaRDI QIDQ5746267zbMATH OpenOpenAlexFDO

Authors N. S. Narayanaswamy, G. Ramakrishna

Publication date 18 February 2014

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.0432

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

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. We consider the problem of computing a minimum average stretch spanning tree in polygonal 2-trees, a super class of 2-connected outerplanar graphs. For a polygonal 2-tree on $n$ vertices, we present an algorithm to compute a minimum average stretch spanning tree in $O(nlogn)$ time. This algorithm also finds a minimum fundamental cycle basis in polygonal 2-trees.

Recommendations

• On minimum average stretch spanning trees in polygonal 2-trees
• On minimum average stretch spanning trees in grid graphs
• scientific article; zbMATH DE number 890671
• The minimum stretch spanning tree problem for typical graphs
• On spanning 2-trees in a graph

Cited in

(2)

• On minimum average stretch spanning trees in polygonal 2-trees
• On minimum average stretch spanning trees in grid graphs

This page was built for publication: On minimum average stretch spanning trees in polygonal 2-trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5746267)