Finding ultrametric minimum-diameter spanning trees

Theoretical Computer Science 2026 Open access

Read full text
Authors: Ching-Lueh Chang
DOI: 10.1016/j.tcs.2026.115769
Cited by: 0
References: 10

Abstract

We show how to find a minimum-diameter spanning tree (resp., the center of a minimum-diameter spanning star) of an n -point ultrametric space in deterministic O ( n ) (resp., O (1)) time.

Fields of Study & Subjects

Complexity and Algorithms in Graphs Computational Geometry and Mesh Generation Algorithms and Data Compression

Publication details

Journal / source
Theoretical Computer Science
Volume
1067
Pages
115769–115769
Publication date
18 January 2026
Language
EN