Optimality computation of the minimum stretch spanning tree problem
| Autor: | Lan Lin, Yixun Lin |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Combinatorics
0209 industrial biotechnology Computational Mathematics 020901 industrial engineering & automation Spanning tree Applied Mathematics Computation 0202 electrical engineering electronic engineering information engineering 020206 networking & telecommunications 02 engineering and technology Hypercube Graph Mathematics |
| Zdroj: | Applied Mathematics and Computation. 386:125502 |
| ISSN: | 0096-3003 |
| DOI: | 10.1016/j.amc.2020.125502 |
| Popis: | The minimum stretch spanning tree problem for a graph G is to find a spanning tree T of G such that the maximum distance in T between two adjacent vertices of G is minimized, where the minimum value is called the tree-stretchof G. There has been extensive study on the algorithmic aspects, such as the NP-hardness and fixed-parameter solvability. We are concerned in this paper with the computation of exact tree-stretch for given graph families. We relate an optimization approach of computing lower and upper bounds. This approach is applied to several typical graph families, such as the hypercubes Qn, the graph products Km × Kn, Pm × Kn, Cm × Cn, Pm × Cn, Pm × Pn, and Km × Cn. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect