Search results for "Tree"
showing 10 items of 1841 documents
On the Low-Dimensional Steiner Minimum Tree Problem in Hamming Metric
2011
It is known that the d-dimensional Steiner Minimum Tree Problem in Hamming metric is NP-complete if d is considered to be a part of the input. On the other hand, it was an open question whether the problem is also NP-complete in fixed dimensions. In this paper we answer this question by showing that the problem is NP-complete for any dimension strictly greater than 2. We also show that the Steiner ratio is 2 - 2/d for d ≥ 2. Using this result, we tailor the analysis of the so-called k-LCA approximation algorithm and show improved approximation guarantees for the special cases d = 3 and d = 4.
The node-depth encoding
2008
The node-depth encoding has elements from direct and indirect encoding for trees which encodes trees by storing the depth of nodes in a list. Node-depth encoding applies specific search operators that is a typical characteristic for direct encodings. An investigation into the bias of the initialization process and the mutation operators of the node-depth encoding shows that the initialization process has a bias to solutions with small depths and diameters, and a bias towards stars. This investigation, also, shows that the mutation operators are unbiased. The performance of node-depth encoding is investigated for the bounded-diameter minimum spanning tree problem. The results are presented f…
A Loopless Generation of Bitstrings without p Consecutive Ones
2001
Let F n (p) be the set of all n-length bitstrings such that there are no p consecutive ls. F n (p) is counted with the pth order Fibonacci numbers and it may be regarded as the subsets of {1, 2,…, n} without p consecutive elements and bitstrings in F n (p) code a particular class of trees or compositions of an integer. In this paper we give a Gray code for F n (p) which can be implemented in a recursive generating algorithm, and finally in a loopless generating algorithm.
Orientation matters
2008
The optimal communication spanning tree (OCST) problem is a well known $\mathcal{NP}$-hard combinatorial optimization problem which seeks a spanning tree that satisfies all given communication requirements for minimal total costs. It has been shown that optimal solutions of OCST problems are biased towards the much simpler minimum spanning tree (MST) problem. Therefore, problem-specific representations for EAs like heuristic variants of edge-sets that are biased towards MSTs show high performance.In this paper, additional properties of optimal solutions for Euclidean variants of OCST problems are studied. Experimental results show that not only edges in optimal trees are biased towards low-…
Random Walks on Weighted Graphs of Groups
2019
Let X be a locally finite simplicial tree without terminal vertices, and let X = ∣X∣1 be its geometric realisation. Let Γ be a nonelementary discrete subgroup of Aut(X).
An algorithm for the solution of tree equations
1997
We consider the problem of solving equations over k-ary trees. Here an equation is a pair of labeled α-ary trees, where α is a function associating an arity to each label. A solution to an equation is a morphism from α-ary trees to k-ary trees that maps the left and right hand side of the equation to the same k-ary tree.
Coding with traces
1994
We prove that the existence of a coding between two trace monoids is decidable for some families of trace monoids. Decidability heavily depends on the structure of the dependence graphs. The concept of coding is based on the new notion of strong morphism between trace monoids.
An algorithm for the Rural Postman problem on a directed graph
1986
The Directed Rural Postman Problem (DRPP) is a general case of the Chinese Postman Problem where a subset of the set of arcs of a given directed graph is ‘required’ to be traversed at minimum cost. If this subset does not form a weakly connected graph but forms a number of disconnected components the problem is NP-Complete, and is also a generalization of the asymmetric Travelling Salesman Problem. In this paper we present a branch and bound algorithm for the exact solution of the DRPP based on bounds computed from Lagrangean Relaxation (with shortest spanning arborescence sub-problems) and on the fathoming of some of the tree nodes by the solution of minimum cost flow problems. Computation…
O(n 2 log n) Time On-Line Construction of Two-Dimensional Suffix Trees
2005
The two-dimensional suffix tree of an n × n square matrix A is a compacted trie that represents all square submatrices of Ai¾?[9]. For the off-line case, i.e., A is given in advance to the algorithm, it is known how to build it in optimal time, for any type of alphabet sizei¾?[9,15]. Motivated by applications in Image Compressioni¾?[18], Giancarlo and Guaianai¾?[12] considered the on-line version of the two-dimensional suffix tree and presented an On2log2n-time algorithm, which we refer to as GG. That algorithm is a non-trivial generalization of Ukkonen's on-line algorithm for standard suffix trees [19]. The main contribution in this paper is an Olog n factor improvement in the time complex…