JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13]


Journal of Information Science and Engineering, Vol. 40 No. 2, pp. 245-251


Enumerating Furthest Pairs in Ultrametric Spaces


HUI-TING CHEN AND CHING-LUEH CHANG+
Department of Computer Science and Engineering
Yuan Ze University
Taoyuan City, 320315 Taiwan
E-mail: s1049102@mail.yzu.edu.tw; clchang@saturn.yzu.edu.tw
+


We prove the following results on enumerating or counting furthest pairs given an ultrametric space with n elements:

• There is a deterministic O(F + nlogn)-time algorithm for enumerating all furthest pairs, where F denotes the total number of furthest pairs.

• There is a Monte Carlo O(n/ε 2 )-time algorithm that estimates the number of furthest pairs to within a multiplicative factor in (1−ε,1+ε), where ε > 0. Furthermore, the time complexity of O(n/ε 2 ) cannot be improved to o(n · f(ε)) for any f(·).


Keywords: ultrametric space, furthest pairs, combinatorial enumeration, counting, Monte Carlo algorithm

  Retrieve PDF document (JISE_202402_03.pdf)