On the tree inclusion problem

We consider the following problem: Given ordered labeled trees S and T can S be obtained from T by deleting nodes? Deletion of the root node u of a subtree with children means replacing the subtree by the trees . For the tree inclusion problem, there can generally be exponentially many ways to obtain the included tree. P. Kilpelinen and H. Mannila [5,7] gave an algorithm based on dynamic programming requiring time and space in the worst case and also on the average for solving this problem. We give an algorithm whose idea is similar to that of [5,7] but which improves the previous one and on the average breaks the barrier. Received: 4 November 1996 / 2 March 2001     

On the bottleneck tree alignment problems

Given a set W of k sequences and a tree T with k leaves labeled with a unique sequence in W, a label tree is used to assign a sequence label to each internal node of the tree T. The cost of a tree edge is defined as the distance, such as the Hamming distance or the Levenshtein (edit) distance, between the sequence labels of a pair of nodes in the edge. The bottleneck edge of a label tree is the edge with the maximum cost in the label tree. The bottleneck tree alignment problem is concerned with the determination of a label tree with minimum cost of the bottleneck edge. A lifted label tree is a label tree in which the sequence label of each internal node is equal to the sequence label of some child of the node. The bottleneck lifted tree alignment problem involves the minimization of cost of the bottleneck edge among all possible lifted label trees of the tree T. This paper shows that when the distance function is a metric, the bottleneck tree alignment problem is NP-complete even when the tree structure resembles a binary tree. For special cases, an exact algorithm is used to solve the bottleneck lifted tree alignment problem in polynomial time. A 2(h-1)-approximation algorithm is used to solve the bottleneck tree alignment problem, where h is the height of the tree T. It is observed that the bound is existentially tight. Finally, this paper shows that any lifted label tree is an optimal solution to the bottleneck tree alignment problem if the distance function is an ultrametric.     

A REVIEW OF TREE CONVEX SETS TEST

A collection of sets may have some interesting properties which help identify efficient algorithms for constraint satisfaction problems and combinatorial auction problems. One of the properties is tree convexity. A collection S of sets is tree convex if we can find a tree T whose nodes are the union of the sets of S and each set of S is the nodes of a subtree of T . This concept extends that of row convex sets each of which is an interval over a total ordering of the elements of the union of these sets. An interesting problem is to find efficient algorithms to test whether a collection of sets is tree convex. It is not known before if there exists a linear time algorithm for this test. In this paper, we review the materials that are the key to a linear algorithm: hypergraphs, a characterization of tree convex sets and the acyclic hypergraph test algorithm. Some typos in the original paper of the acyclicity test are corrected here. Some experiments show that the linear algorithm is significantly faster than a well‐known existing algorithm.     

Minimum Cost Partitions of Trees with Supply and Demand

Let T be a given tree. Each vertex of T is either a supply vertex or a demand vertex, and is assigned a positive integer, called the supply or the demand. Every demand vertex v of T must be supplied an amount of ??power,?? equal to the demand of v, from exactly one supply vertex through edges in T. Each edge e of T has a direction, and is assigned a positive integer which represents the cost required to delete e from T or reverse the direction of e. Then one wishes to obtain subtrees of T by deleting edges or reversing the directions of edges so that (a)?each subtree contains exactly one supply vertex whose supply is no less than the sum of all demands in the subtree and (b)?every edge is directed away from the supply vertex in each subtree. One wishes to minimize the total cost to obtain such subtrees from T. In the paper, we first show that this minimization problem is NP-hard, and then give a pseudo-polynomial-time algorithm to solve the problem. We finally give a fully polynomial-time approximation scheme (FPTAS) for the problem.     

An improved algorithm for finding a length-constrained maximum-density subtree in a tree

Given a tree T with weight and length on each edge, as well as a lower bound L and an upper bound U, the so-called length-constrained maximum-density subtree problem is to find a maximum-density subtree in T such that the length of this subtree is between L and U. In this study, we present an algorithm that runs in O(nUlogn) time for the case when the edge lengths are positive integers, where n is the number of nodes in T, which is an improvement over the previous algorithms when U=Ω(logn). In addition, we show that the time complexity of our algorithm can be reduced to , when the edge lengths being considered are uniform.     

Linear time algorithms for finding and representing all the tandem repeats in a string

A tandem repeat (or square) is a string αα, where α is a non-empty string. We present an O(|S|)-time algorithm that operates on the suffix tree T(S) for a string S, finding and marking the endpoint in T(S) of every tandem repeat that occurs in S. This decorated suffix tree implicitly represents all occurrences of tandem repeats in S, and can be used to efficiently solve many questions concerning tandem repeats and tandem arrays in S. This improves and generalizes several prior efforts to efficiently capture large subsets of tandem repeats.     

Improved Approximation Algorithms for the Min-max Tree Cover and Bounded Tree Cover Problems

In this paper we provide improved approximation algorithms for the Min-Max Tree Cover and Bounded Tree Cover problems. Given a graph G=(V,E) with weights w:E→?⁺, a set T ₁,T ₂,…,T _k of subtrees of G is called a tree cover of G if $V=\bigcup_{i=1}^{k} V(T_{i})$ . In the Min-Max k-tree Cover problem we are given graph G and a positive integer k and the goal is to find a tree cover with k trees, such that the weight of the largest tree in the cover is minimized. We present a 3-approximation algorithm for this improving the two different approximation algorithms presented in Arkin et al. (J. Algorithms 59:1–18, 2006) and Even et al. (Oper. Res. Lett. 32(4):309–315, 2004) with ratio 4. The problem is known to have an APX-hardness lower bound of $\frac{3}{2}$ (Xu and Wen in Oper. Res. Lett. 38:169–173, 2010). In the Bounded Tree Cover problem we are given graph G and a bound λ and the goal is to find a tree cover with minimum number of trees such that each tree has weight at most λ. We present a 2.5-approximation algorithm for this, improving the 3-approximation bound in Arkin et al. (J. Algorithms 59:1–18, 2006).     

The weight-constrained maximum-density subtree problem and related problems in trees

Given a tree T=(V,E) of n nodes such that each node v is associated with a value-weight pair (val _v ,w _v ), where value val _v is a real number and weight w _v is a non-negative integer, the density of T is defined as \(\frac{\sum_{v\in V}{\mathit{val}}_{v}}{\sum_{v\in V}w_{v}}\). A subtree of T is a connected subgraph (V′,E′) of T, where V′?V and E′?E. Given two integers w _min? and w _max?, the weight-constrained maximum-density subtree problem on T is to find a maximum-density subtree T′=(V′,E′) satisfying w _min?≤∑_v∈V′ w _v ≤w _max?. In this paper, we first present an O(w _max? n)-time algorithm to find a weight-constrained maximum-density path in a tree T, and then present an O(w _max? ² n)-time algorithm to find a weight-constrained maximum-density subtree in T. Finally, given a node subset S?V, we also present an O(w _max? ² n)-time algorithm to find a weight-constrained maximum-density subtree in T which covers all the nodes in S.     

Distributed algorithms for finding and maintaining a k-tree core in a dynamic network

A k-core C_k of a tree T is subtree with exactly k leaves for k?n_l, where n_l the number of leaves in T, and minimizes the sum of the distances of all nodes from C_k. In this paper first we propose a distributed algorithm for constructing a rooted spanning tree of a dynamic graph such that root of the tree is located near the center of the graph. Then we provide a distributed algorithm for finding k-core of that spanning tree. The spanning tree is constructed in two stages. In the first stage, a forest of trees is generated. In the next stage these trees are connected to form a single rooted tree. An interesting aspect of the first stage of proposed spanning algorithm is that it implicitly constructs the (convex) hull of those nodes which are not already included in the spanning forest. The process is repeated till all non root nodes of the graph have chosen a unique parent. We implemented the algorithms for finding spanning tree and its k-core. A core can be quite useful for routing messages in a dynamic network consisting of a set of mobile devices.     

Approximating the minmax rooted-tree cover in a tree

Given an edge-weighted rooted tree T and a positive integer p (?n), where n is the number of vertices in T, we cover all vertices in T by a set of p subtrees each of which contains the root r of T. The minmax rooted-tree cover problem asks to find such a set of p subtrees so as to minimize the maximum weight of the subtrees in the set. In this paper, we propose an O(n) time (2+ε)-approximation algorithm to the problem, where ε>0 is a prescribed constant.     

Approximating Optimal Binary Decision Trees

We give a (ln?n+1)-approximation for the decision tree (DT) problem. An instance of DT is a set of m binary tests T=(T ₁,…,T _m ) and a set of n items X=(X ₁,…,X _n ). The goal is to output a binary tree where each internal node is a test, each leaf is an item and the total external path length of the tree is minimized. Total external path length is the sum of the depths of all the leaves in the tree. DT has a long history in computer science with applications ranging from medical diagnosis to experiment design. It also generalizes the problem of finding optimal average-case search strategies in partially ordered sets which includes several alphabetic tree problems. Our work decreases the previous best upper bound on the approximation ratio by a constant factor. We provide a new analysis of the greedy algorithm that uses a simple accounting scheme to spread the cost of a tree among pairs of items split at a particular node. We conclude by showing that our upper bound also holds for the DT problem with weighted tests.     

Improved Approximation Algorithms for the Average-Case Tree Searching Problem

We study the following tree search problem: in a given tree T=(V,E) a vertex has been marked and we want to identify it. In order to locate the marked vertex, we can use edge queries. An edge query e asks in which of the two connected components of T?e the marked vertex lies. The worst-case scenario where one is interested in minimizing the maximum number of queries is well understood, and linear time algorithms are known for finding an optimal search strategy. Here we study the more involved average-case analysis: A function w:V→?⁺ is given which measures the likelihood for a vertex to be the one marked, and we seek to determine the strategy (decision tree) that minimizes the weighted average number of queries. In a companion paper we prove that the above tree search problem is $\mathcal {NP}$ -complete even for the class of trees of bounded diameter or bounded degree. Here, we match this complexity result with a tight algorithmic analysis of the bounded degree instances. We show that any optimal strategy (i.e., one that minimizes the weighted average number of queries) performs at most O(Δ(T)(log|V|+log(w(T)/w _min))) queries in the worst case, where w(T) is the sum of the likelihoods of the vertices of T, w _min is the minimum positive likelihood over the vertices of T and Δ(T) is the maximum degree of T. We combine this result with a non-trivial exponential time algorithm to provide an FPTAS for trees with bounded degree. We also show that for unbounded instances a natural greedy strategy attains a 1.62-approximation, improving upon the best known 14-approximation guarantee, previously provided by two of the authors.     

Mining rooted ordered trees under subtree homeomorphism

Mining frequent tree patterns has many applications in different areas such as XML data, bioinformatics and World Wide Web. The crucial step in frequent pattern mining is frequency counting, which involves a matching operator to find occurrences (instances) of a tree pattern in a given collection of trees. A widely used matching operator for tree-structured data is subtree homeomorphism, where an edge in the tree pattern is mapped onto an ancestor-descendant relationship in the given tree. Tree patterns that are frequent under subtree homeomorphism are usually called embedded patterns. In this paper, we present an efficient algorithm for subtree homeomorphism with application to frequent pattern mining. We propose a compact data-structure, called occ, which stores only information about the rightmost paths of occurrences and hence can encode and represent several occurrences of a tree pattern. We then define efficient join operations on the occ data-structure, which help us count occurrences of tree patterns according to occurrences of their proper subtrees. Based on the proposed subtree homeomorphism method, we develop an effective pattern mining algorithm, called TPMiner. We evaluate the efficiency of TPMiner on several real-world and synthetic datasets. Our extensive experiments confirm that TPMiner always outperforms well-known existing algorithms, and in several cases the improvement with respect to existing algorithms is significant.     

Minimizing the makespan in a single machine scheduling problem with a time-based learning effect

Both the building cost and the multiple-source routing cost are important considerations in construction of a network system. A spanning tree with minimum building cost among all spanning trees is called a minimum spanning tree (MST), and a spanning tree with minimum k-source routing cost among all spanning trees is called a k-source minimum routing cost spanning tree (k-MRCT). This paper proposes an algorithm to construct a spanning tree T for a metric graph G with a source vertex set S such that the building cost of T is at most 1+2/(α−1) times of that of an MST of G, and the k-source routing cost of T is at most α(1+2(k−1)(n−2)/k(n+k−2)) times of that of a k-MRCT of G with respect to S, where α>1, k=|S| and n is the number of vertices of G.     

Scheduling time-constrained multicast messages in circuit-switched tree networks

In this paper, we consider a kind of multicast scheduling problem in a tree network. Each multicast message is transmitted through a directed subtree within the tree network. The transmission time of each multicast message is assumed to be one unit. Two messages can be transmitted at the same time if their subtrees are edge-disjoint. Each message is constrained by a ready time and a deadline, and has a weight we can gain if it is scheduled within its deadline. The optimality criterion is the total weight we gain. We assume that the degree of each subtree is bounded by a constant d and present an approximation algorithm of which the approximation ratio is at most 4d+15.     

On embedding subclasses of height-balanced trees in hypercubes

A height-balanced tree is a rooted binary tree T in which for every vertex v∈V(T), the heights of the subtrees, rooted at the left and right child of v, differ by at most one; this difference is called the balance factor of v. These trees are extensively used as data structures for sorting and searching. We embed several subclasses of height-balanced trees of height h in Q_h+1 under certain conditions. In particular, if a tree T is such that the balance factor of every vertex in the first three levels is arbitrary (0 or 1) and the balance factor of every other vertex is zero, then we prove that T is embeddable in its optimal hypercube with dilation 1 or 2 according to whether it is balanced or not.     

Fractal analysis of temporal variation of air pollutant concentration by box counting

The scale-invariant behavior of air pollutant concentration (APC) time structure was investigated by applying the box counting method to APC time series. One-year series of hourly average APC observations, including O₃, CO, SO₂, NO, NO₂, and PM10 which were obtained from urban, traffic, and national park air monitoring station at Taipei (Taiwan), were transferred into a useful compact form through this method, namely, the box-dimension (D_B)-threshold (T_h) and critical scale (C_S)-threshold (T_h) plots. The validity of this approach was supported with the result that the practical implications of D_B-T_h (or C_S-T_h) plots could be interpreted in terms of traditional statistical parameters. Since the dependences of both D_B and C_S on the T_h values were closely related to the variation of APC in time, they were used to characterize the temporal distribution of APC. The analysis confirmed the existence of scale invariance in those investigated APC time series. Moreover, the D_B (C_S) was shown to be a decreasing (increasing) function of the threshold level, implying multifractal characteristics, i.e. the weak and intense regions scale differently. Some practical applications based on the box counting method were also discussed.     

A series of approximation algorithms for the acyclic directed steiner tree problem

Given an acyclic directed network, a subsetS of nodes (terminals), and a rootr, theacyclic directed Steiner tree problem requires a minimum-cost subnetwork which contains paths fromr to each terminal. It is known that unlessNP⊆DTIME[n ^polylogn ] no polynomial-time algorithm can guarantee better than (lnk)/4-approximation, wherek is the number of terminals. In this paper we give anO(k ^ε)-approximation algorithm for any ε>0. This result improves the previously knownk-approximation. This research was supported in part by Volkswagen-Stiftung and Packard Foundation.     

Algorithms for solving the symmetry number problem on trees

The symmetry number of a tree is defined as the number of nodes of the maximum subtree of the tree that exhibits axial symmetry. Chin and Yen have presented an algorithm for solving the problem of finding the symmetry number of unrooted unordered trees in time O(n⁴). In this paper we present an improved algorithm for solving the symmetry number problem on trees that runs in time O(n³). We also show that our algorithm needs O(n²logn) time for trees with bounded degrees.     

A note on the minimum label spanning tree

We give a tight analysis of the greedy algorithm introduced by Krumke and Wirth for the minimum label spanning tree problem. The algorithm is shown to be a (ln(n−1)+1)-approximation for any graph with n nodes (n>1), which improves the known performance guarantee 2lnn+1.