Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn $O(n log n)$ time Algorithm for computing the Path-length Distance between Trees
120
0
0.0
(
0
)
Added by
David Bryant
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Tree comparison metrics have proven to be an invaluable aide in the reconstruction and analysis of phylogenetic (evolutionary) trees. The path-length distance between trees is a particularly attractive measure as it reflects differences in tree shape as well as differences between branch lengths. The distance equals the sum, over all pairs of taxa, of the squared differences between the lengths of the unique path connecting them in each tree. We describe an $O(n log n)$ time for computing this distance, making extensive use of tree decomposition techniques introduced by Brodal et al. (2004).
rate research
Read More
The {em longest common subsequence (LCS)} problem is a classic and well-studied problem in computer science. LCS is a central problem in stringology and finds broad applications in text compression, error-detecting codes and biological sequence comparison. However, in numerous contexts, words represent cyclic sequences of symbols and LCS must be generalized to consider all circular shifts of the strings. This occurs especially in computational biology when genetic material is sequenced form circular DNA or RNA molecules. This initiates the problem of {em longest common cyclic subsequence (LCCS)} which finds the longest subsequence between all circular shifts of two strings. In this paper, we give an $O(n^2)$ algorithm for solving LCCS problem where $n$ is the number of symbols in the strings.
In the Survivable Network Design problem (SNDP), we are given an undirected graph $G(V,E)$ with costs on edges, along with a connectivity requirement $r(u,v)$ for each pair $u,v$ of vertices. The goal is to find a minimum-cost subset $E^*$ of edges, that satisfies the given set of pairwise connectivity requirements. In the edge-connectivity version we need to ensure that there are $r(u,v)$ edge-disjoint paths for every pair $u, v$ of vertices, while in the vertex-connectivity version the paths are required to be vertex-disjoint. The edge-connectivity version of SNDP is known to have a 2-approximation. However, no non-trivial approximation algorithm has been known so far for the vertex version of SNDP, except for special cases of the problem. We present an extremely simple algorithm to achieve an $O(k^3 log n)$-approximation for this problem, where $k$ denotes the maximum connectivity requirement, and $n$ denotes the number of vertices. We also give a simple proof of the recently discovered $O(k^2 log n)$-approximation result for the single-source version of vertex-connectivity SNDP. We note that in both cases, our analysis in fact yields slightly better guarantees in that the $log n$ term in the approximation guarantee can be replaced with a $log tau$ term where $tau$ denotes the number of distinct vertices that participate in one or more pairs with a positive connectivity requirement.
In population protocols, the underlying distributed network consists of $n$ nodes (or agents), denoted by $V$, and a scheduler that continuously selects uniformly random pairs of nodes to interact. When two nodes interact, their states are updated by applying a state transition function that depends only on the states of the two nodes prior to the interaction. The efficiency of a population protocol is measured in terms of both time (which is the number of interactions until the nodes collectively have a valid output) and the number of possible states of nodes used by the protocol. By convention, we consider the parallel time cost, which is the time divided by $n$. In this paper we consider the majority problem, where each node receives as input a color that is either black or white, and the goal is to have all of the nodes output the color that is the majority of the input colors. We design a population protocol that solves the majority problem in $O(log^{3/2}n)$ parallel time, both with high probability and in expectation, while using $O(log n)$ states. Our protocol improves on a recent protocol of Berenbrink et al. that runs in $O(log^{5/3}n)$ parallel time, both with high probability and in expectation, using $O(log n)$ states.
This paper considers the online machine minimization problem, a basic real time scheduling problem. The setting for this problem consists of n jobs that arrive over time, where each job has a deadline by which it must be completed. The goal is to design an online scheduler that feasibly schedules the jobs on a nearly minimal number of machines. An algorithm is c-machine optimal if the algorithm will feasibly schedule a collection of jobs on cm machines if there exists a feasible schedule on m machines. For over two decades the best known result was a O(log P)-machine optimal algorithm, where P is the ratio of the maximum to minimum job size. In a recent breakthrough, a O(log m)-machine optimal algorithm was given. In this paper, we exponentially improve on this recent result by giving a O(log log m)-machine optimal algorithm.
Consider a metric space $(P,dist)$ with $N$ points whose doubling dimension is a constant. We present a simple, randomized, and recursive algorithm that computes, in $O(N log N)$ expected time, the closest-pair distance in $P$. To generate recursive calls, we use previous results of Har-Peled and Mendel, and Abam and Har-Peled for computing a sparse annulus that separates the points in a balanced way.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
