An efficient algorithm for isometrically embedding weighted trees into low-dimensional ℓ∞-normed spaces

作者：

Highlights：

• An efficient algorithm for isometrically embedding weighted trees is presented.

• The proposed algorithm relies upon an independent tree-splitting procedure.

• The algorithm maps an n-vertex weighted tree onto an integer-valued vector.

• The overall running time of the proposed algorithm is Θ(nlog2n).

摘要

•An efficient algorithm for isometrically embedding weighted trees is presented.•The proposed algorithm relies upon an independent tree-splitting procedure.•The algorithm maps an n-vertex weighted tree onto an integer-valued vector.•The overall running time of the proposed algorithm is Θ(nlog2n).

论文关键词：Exact algorithm,Isometric embedding,Maximum norm

论文评审过程：Received 3 November 2021, Revised 11 June 2022, Accepted 15 June 2022, Available online 19 June 2022, Version of Record 4 July 2022.

论文官网地址：https://doi.org/10.1016/j.knosys.2022.109284