Optimal Algorithm for Finding Representation of Subtree Distance

作     者：Maehara, Takanori Ando, Kazutoshi 

作者机构：RIKEN Ctr Adv Intelligence Project Discrete Optimizat Unit Tokyo Japan Shizuoka Univ Dept Math & Syst Engn Shizuoka Japan 

出 版 物：《IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES》 (IEICE Trans Fund Electron Commun Comput Sci)

年 卷 期：2022年第E105卷第8期

页      面：1203-1210页

核心收录：

学科分类：0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Japan Society for the Promotion of Science  KAKENHI [15K00033  18K11180] 

主　　题：graph algorithm phylogenetic tree tree metric subtree distance 

摘      要：In this paper, we address the problem of finding a representation of a subtree distance, which is an extension of a tree metric. We show that a minimal representation is uniquely determined by a given subtree distance, and give an O(n(2)) time algorithm that finds such a representation, where n is the size of the ground set. Since a lower bound of the problem is Omega(n(2)), our algorithm achieves the optimal time complexity.