IEICE TRANSACTIONS on Fundamentals
Optimal Algorithm for Finding Representation of Subtree Distance
Summary :
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(n2) time algorithm that finds such a representation, where n is the size of the ground set. Since a lower bound of the problem is Ω(n2), our algorithm achieves the optimal time complexity.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E105-A No.9 pp.1203-1210
- Publication Date
- 2022/09/01
- Publicized
- 2022/04/19
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.2021DMP0014
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
- Algorithms and Data Structures, Graphs and Networks
Authors
Takanori MAEHARA
RIKEN Center for Advanced Intelligence Project
Kazutoshi ANDO
Shizuoka University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Takanori MAEHARA, Kazutoshi ANDO, "Optimal Algorithm for Finding Representation of Subtree Distance" in IEICE TRANSACTIONS on Fundamentals,
vol. E105-A, no. 9, pp. 1203-1210, September 2022, doi: 10.1587/transfun.2021DMP0014.
Abstract: 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(n2) time algorithm that finds such a representation, where n is the size of the ground set. Since a lower bound of the problem is Ω(n2), our algorithm achieves the optimal time complexity.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2021DMP0014/_p
Copy
@ARTICLE{e105-a_9_1203,
author={Takanori MAEHARA, Kazutoshi ANDO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Optimal Algorithm for Finding Representation of Subtree Distance},
year={2022},
volume={E105-A},
number={9},
pages={1203-1210},
abstract={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(n2) time algorithm that finds such a representation, where n is the size of the ground set. Since a lower bound of the problem is Ω(n2), our algorithm achieves the optimal time complexity.},
keywords={},
doi={10.1587/transfun.2021DMP0014},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - Optimal Algorithm for Finding Representation of Subtree Distance
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1203
EP - 1210
AU - Takanori MAEHARA
AU - Kazutoshi ANDO
PY - 2022
DO - 10.1587/transfun.2021DMP0014
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E105-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2022
AB - 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(n2) time algorithm that finds such a representation, where n is the size of the ground set. Since a lower bound of the problem is Ω(n2), our algorithm achieves the optimal time complexity.
ER -
English
