JCSE, vol. 13, no. 1, pp.11-16, 2019

DOI: http://dx.doi.org/10.5626/JCSE.2019.13.1.11

Enumerating Subsequences of a Sequence and Paths of a Tree in the Order of Weight

Sung Kwon Kim
School of Computer Science and Engineering, Chung-Ang University, Seoul, Korea

Abstract: The following two enumeration problems are addressed: (i) given a sequence A of n real numbers, the subsequences of A in the order of their weight (or sum), and (ii) given an n-vertex edge-weighted tree T, the paths of T in the order of their weight. We show that both enumerations (i) and (ii) can be done in O(n2 log n) time and the data structures for (i) can be constructed in O(n log n) time using O(n) space, and data structures for (ii) can be built in O(n log n) time using O(n log n) space.

Keyword: Algorithm; Enumeration; Subsequences of sequence; Paths of tree

Full Paper:   263 Downloads, 1295 View