12 papers · ranked by Valyu relevance
J.G. Gardiner, Lachlan L. H. Andrew, Junhao Gan, Jean Honorio + 1 more
'Seeun William Umboh'] This paper tightens the best known analysis of Hein's 1989 algorithm to infer the topology of a weighted tree based on the lengths of paths between its leaves. It shows that the number of length queries required for a degree-k tree of n leaves is O(nk logk n), which is the lower bound. It also…
Romain Azaïs, Jean-Baptiste Durand, Christophe Godin
The class of self-nested trees presents remarkable compression properties because of the systematic repetition of subtrees in their structure. In this paper, we provide a better combinatorial characterization of this specific family of trees. In particular, we show from both theoretical and practical viewpoints that…
Mateusz Pawlik, Nikolaus Augsten
We consider the classical tree edit distance between ordered labeled trees, which is defined as the minimum-cost sequence of node edit operations that transform one tree into another. The state-of-the-art solutions for the tree edit distance are not satisfactory. The main competitors in the field either have optimal…
Frédéric Magniez, Ashwin Nayak, Miklós Sántha, Jonah Sherman + 2 more
'Gábor Tardos' 'David Xiao'] We consider the randomized decision tree complexity of the recursive 3-majority function. We prove a lower bound of (1/2 − δ) · 2.57143h for the two-sided-error randomized decision tree complexity of evaluating height h formulae with error δ ∈ [0, 1/2). This improves the lower bound of (1 −…
Eric Blais, Li-Yang Tan, Andrew Wan
We give a new bound on the sum of the linear Fourier coefficients of a Boolean function in terms of its parity decision tree complexity. This result generalizes an inequality of O'Donnell and Servedio for regular decision trees [OS08]. We use this bound to obtain the first non-trivial lower bound on the parity decision…
Hong‐Yan Zhang, Yu Zhou, Zhiqiang Feng
Zernike radial polynomials (ZRP) play a significant role in application areas such as optics design, imaging systems, and image processing systems. Currently, there are two kinds of numerical schemes for computing the ZRP automatically with computer programs: one is based on the definition in which the factorial…
Ethan Torres, R.S. Sreenivas, Richard B. Sowers
Recombining trinomial trees are a workhorse for modeling discrete-event systems in option pricing, logistics, and feedback control. Because each node stores a state-dependent quantity, a depth-D tree na¨ıvely yields O(3D) trajectories, making exhaustive enumeration infeasible. Under time-homogeneous dynamics, however…
Akshar Varma
The rooted tree is an important data structure, and the subtree size, height, and depth are naturally defined attributes of every node. We consider the problem of the existence of a k-ary tree given a list of attribute sequences. We give polynomial time (O(n log(n))) algorithms for the existence of a k-ary tree given…
Romain Azaïs
Self-nested trees present a systematic form of redundancy in their subtrees and thus achieve optimal compression rates by DAG compression. A method for quantifying the degree of self-similarity of plants through self-nested trees has been introduced by Godin and Ferraro in 2010. The procedure consists in computing a…
Shihyen Chen
An ordered labeled tree is a tree in which the nodes are labeled and the left-to-right order among siblings is relevant. The edit distance between two ordered labeled trees is the minimum cost of changing one tree into the other through a sequence of edit steps. In the literature, there are a class of algorithms based…
Tianqi Yang
Tree path minimum query problem is a fundamental problem while processing trees, and is used widely in minimum spanning tree verification and randomized minimum spanning tree algorithms. In this paper, we study the possibility of building an oracle in advance, which is able to answer the queries efficiently. We present…
Nishant Doshi
The complexity of an algorithm is an important parameter to determine its efficiency. They are of different types viz. Time complexity, Space complexity, etc. However, none of them consider the execution path as a complexity measure. Ashok et al, firstly proposed the notion of the Path Complexity of a…