Minimum Stretch Spanning Tree Problem in Operations on Trees

Autor:	Toru Araki, Eito Hasegawa, Shion Kato
Rok vydání:	2022
Předmět:	TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Computer Networks and Communications Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) MathematicsofComputing_DISCRETEMATHEMATICS
Zdroj:	Journal of Interconnection Networks. 22
ISSN:	1793-6713 0219-2659
DOI:	10.1142/s0219265921500286
Popis:	The minimum stretch spanning tree problem for a connected graph [Formula: see text] is to find a spanning tree [Formula: see text] of [Formula: see text] such that the maximum distance in [Formula: see text] between two adjacent vertices of [Formula: see text] is minimized, where the minimum value is called the tree-stretch of [Formula: see text]. This paper presents the tree-stretch of a graph constructed by the Cartesian product of two trees. This result is a generalization of the result for the grid graphs obtained by Lin and Lin (L. Lin, Y. Lin, The minimum stretch spanning tree problem for typical graphs, Acta Mathematicae Applicatae Sinica, English Series, 37(3) (2021) 510–522). Then, we give the tree-stretch of the [Formula: see text]-th power of a tree.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::87821c325d28e7cfcc40e7665c0bd2e7 https://doi.org/10.1142/s0219265921500286 Zobrazit plný text záznamu