Improving on-line construction of two-dimensional suffix trees for square matrices

The two-dimensional (2-D) suffix tree of an n×n square matrix A is a compacted trie that represents all square submatrices of A. We consider constructing 2-D suffix trees on-line, which means, instead of giving the whole matrix A in advance, A is separated and each part of A is given at different time as algorithms proceed. In general, developing an on-line algorithm is more difficult than developing an off-line algorithm. Moreover, the smaller the input grain size is, the harder it is to develop an on-line algorithm. In the case of 2-D suffix tree construction, dealing with a character at a time is harder than dealing with a row or a column at a time.In this paper we propose a randomized linear-time algorithm for constructing 2-D suffix trees on-line. This algorithm is superior to previous algorithms in two ways: (1) This is the first linear-time algorithm for constructing 2-D suffix trees on-line. Although there have been some linear-time algorithms for off-line construction, there were no linear-time algorithms for on-line construction. (2) We deal with the most fine-grain on-line case, i.e., our algorithm can construct a 2-D suffix tree even though only one character of A is given at a time, while previous on-line algorithms require at least a row and/or a column at a time.     

Constructing independent spanning trees for locally twisted cubes

The independent spanning trees (ISTs) problem attempts to construct a set of pairwise independent spanning trees and it has numerous applications in networks such as data broadcasting, scattering and reliable communication protocols. The well-known ISTs conjecture, Vertex/Edge Conjecture, states that any n-connected/n-edge-connected graph has n vertex-ISTs/edge-ISTs rooted at an arbitrary vertex r. It has been shown that the Vertex Conjecture implies the Edge Conjecture. In this paper, we consider the independent spanning trees problem on the n-dimensional locally twisted cube LTQ_n. The very recent algorithm proposed by Hsieh and Tu (2009) [12] is designed to construct n edge-ISTs rooted at vertex 0 for LTQ_n. However, we find out that LTQ_n is not vertex-transitive when n≥4; therefore Hsieh and Tu’s result does not solve the Edge Conjecture for LTQ_n. In this paper, we propose an algorithm for constructing n vertex-ISTs for LTQ_n; consequently, we confirm the Vertex Conjecture (and hence also the Edge Conjecture) for LTQ_n.     

Maintaining Spanning Trees of Small Diameter

Given a graph G with m edges and n nodes, a spanning tree T of G , and an edge e that is being deleted from or inserted into G , we give efficient O(n) algorithms to compute a possible swap for e that minimizes the diameter of the new spanning tree. This problem arises in high-speed networks, particularly in optical networks. Received January 1995; revised February 1997.     

A speed-up for the commute between subword trees and DAWGs

A popular way to describe and build the DAWG or Directed Acyclic Word Graph of a string is by transformation of the corresponding subword tree. This transformation, which is not difficult to reverse, is easy to grasp and almost trivial to implement except for the assumed implication of a standard tree isomorphism algorithm. Here we point out a simple property of subword trees that makes checking tree isomorphism in this context a straightforward process, thereby simplifying the transformation significantly. Subword trees and DAWGs arise rather ubiquitously in applications of string processing, where they often play complementary roles. Efficient conversions are thus especially desirable.     

Building species trees from larger parts of phylogenomic databases

Gene trees are leaf-labeled trees inferred from molecular sequences. Because of gene duplication events arising in genomes, some species host several copies of the same gene, hence individual gene trees usually have several leaves labeled with identical species names. Dealing with such multi-labeled gene trees (MUL trees) is a substantial problem in phylogenomics, e.g. current supertree methods do not handle MUL trees, which restricts studies aimed at building the Tree of Life to a very small core of mono-copy genes. We propose to tackle this problem by mainly transforming a collection of MUL trees into a collection of trees, each containing single copies of labels. To achieve that aim, we provide several fast algorithmic building stones and describe how they fit in a general framework to build a species tree. First, we propose to separately preprocess each MUL tree in order to remove its redundant parts with respect to speciation events. For this purpose, we present a tree isomorphism algorithm for MUL trees to reduce redundant parts of these trees. Second, we show how the speciation signal contained in a MUL tree can be represented by a linear set of triplets. When this set is topologically coherent (compatible), we show that it can be used to produce a single-copy gene tree to replace the MUL tree while preserving the information it contains on speciation events. As an alternative approach, we propose to extract from each MUL tree a maximum size subtree that is free of duplication events. The algorithms are finally applied in a supertree analysis of hogenom, a database of homologous genes from fully sequenced genomes.     

Finding a maximum-density path in a tree under the weight and length constraints

Let T=(V,E) be a tree with n nodes such that each node v is associated with a value-weight pair(valv,wv), where the valuevalv is a real number and the weightwv is a positive integer. The density of a path P=〈v₁,v₂,…,vk〉 is defined as . The weight of P, denoted by w(P), is . Given a tree of n nodes, two integers wmin and wmax, and a length lower bound L, we present a pseudo-polynomial O(wmaxnL)-time algorithm to find a maximum-density path P in T such that wmin?w(P)?wmax and the length of P is at least L.     

Faster two-dimensional pattern matching with rotations

The most efficient currently known algorithms for two-dimensional pattern matching with rotations have a worst case time complexity of O(n²m³)$\mathrm{O}(n^2{m}^3)$, where the size of the text is n×n$n\times n$ and the size of the pattern is m×m$m\times m$. In this paper we present a new algorithm for the problem whose running time is O(n²m²)$\mathrm{O}(n^2{m}^2)$.     

The interval-merging problem

A closed interval is an ordered pair of real numbers [x, y], with x ? y. The interval [x, y] represents the set {i ∈ R∣x ? i ? y}. Given a set of closed intervals I={[a₁,b₁],[a₂,b₂],…,[a_k,b_k]}, the Interval-Merging Problem is to find a minimum-cardinality set of intervals M(I)={[x₁,y₁],[x₂,y₂],…,[x_j,y_j]}, j ? k, such that the real numbers represented by equal those represented by . In this paper, we show the problem can be solved in O(d log d) sequential time, and in O(log d) parallel time using O(d) processors on an EREW PRAM, where d is the number of the endpoints of I. Moreover, if the input is given as a set of sorted endpoints, then the problem can be solved in O(d) sequential time, and in O(log d) parallel time using O(d/log d) processors on an EREW PRAM.     

Graph construction with the maximum number of trees by continuous edge addition

A simple computational algorithm is presented to construct a graph with the maximum number of trees by adding edges one by one. The number of trees of a graph would become an index to estimate the overall reliability of probabilistic communication networks with the same link probabilities. Our procedure, Max-trees, selects one edge that gives the maximum number of trees among edges not included in the original graph. This process is continuously repeated at each step of adding an edge, when we get the sequence of new edges to be added. As examples of the execution results, the edge sequence and the maximum number of trees are shown for two types of starting graph, which are a tree of series edges and a star-shaped tree for nodes n = 7 and 8. To see how many trees these graphs have, the minimum numbers of trees for graphs with the same number of nodes and edges are similarly calculated by the minimum-version algorithm Min-trees. An edge sequence of Max-trees makes long cycles, and that of Min-trees makes cycles of three for as long as possible. The ratio of the maximum number of trees to the minimum number of trees is about 1 to 6 for these examples. This work was presented in part at the 11th International Symposium on Artificial Life and Robotics, Oita, Japan, January 23–25, 2006     

Bounded Degree Interval Sandwich Problems

The problems of Interval Sandwich (IS) and Intervalizing Colored Graphs (ICG) have received a lot of attention recently, due to their applicability to DNA physical mapping problems with ambiguous data. Most of the results obtained so far on the problems were hardness results. Here we study the problems under assumptions of sparseness, which hold in the biological context. We prove that both problems are polynomial when either (1) the input graph degree and the solution graph clique size are bounded, or (2) the solution graph degree is bounded. In particular, this implies that ICG is polynomial on bounded degree graphs for every fixed number of colors, in contrast with the recent result of Bodlaender and de Fluiter. Received October 2, 1997; revised April 1, 1998.     

Strongly polynomial-time truthful mechanisms in one shot

One of the main challenges in algorithmic mechanism design is to turn (existing) efficient algorithmic solutions into efficient truthful mechanisms. Building a truthful mechanism is indeed a difficult process since the underlying algorithm must obey certain “monotonicity” properties and suitable payment functions need to be computed (this task usually represents the bottleneck in the overall time complexity).     

Improved Algorithms and Complexity Results for Power Domination in Graphs

The NP-complete Power Dominating Set problem is an “electric power networks variant” of the classical domination problem in graphs: Given an undirected graph G=(V,E), find a minimum-size set P?V such that all vertices in V are “observed” by the vertices in P. Herein, a vertex observes itself and all its neighbors, and if an observed vertex has all but one of its neighbors observed, then the remaining neighbor becomes observed as well. We show that Power Dominating Set can be solved by “bounded-treewidth dynamic programs.” For treewidth being upper-bounded by a constant, we achieve a linear-time algorithm. In particular, we present a simplified linear-time algorithm for Power Dominating Set in trees. Moreover, we simplify and extend several NP-completeness results, particularly showing that Power Dominating Set remains NP-complete for planar graphs, for circle graphs, and for split graphs. Specifically, our improved reductions imply that Power Dominating Set parameterized by |P| is W[2]-hard and it cannot be better approximated than Dominating Set.     

Real Two Dimensional Scaled Matching

Scaled Matching refers to the problem of finding all locations in the text where the pattern, proportionally enlarged according to an arbitrary real-sized scale, appears. Scaled matching is an important problem that was originally inspired by Computer Vision. Finding a combinatorial definition that captures the concept of real scaling in discrete images has been a challenge in the pattern matching field. No definition existed that captured the concept of real scaling in discrete images, without assuming an underlying continuous signal, as done in the image processing field. We present a combinatorial definition for real scaled matching that scales images in a pleasing natural manner. We also present efficient algorithms for real scaled matching. The running times of our algorithms are as follows. For T, a two-dimensional n×n text array, and P, an m×m pattern array, we find in T all occurrences of P scaled to any real value in time O(nm ³+n ² mlog m). Research of A. Amir partially supported by ISF grant 282/01 and NSF grant CCR-01-04494.     

Uniquely Restricted Matchings

A matching in a graph is a set of edges no two of which share a common vertex. In this paper we introduce a new, specialized type of matching which we call uniquely restricted matchings, originally motivated by the problem of determining a lower bound on the rank of a matrix having a specified zero/ non-zero pattern. A uniquely restricted matching is defined to be a matching M whose saturated vertices induce a subgraph which has only one perfect matching, namely M itself. We introduce the two problems of recognizing a uniquely restricted matching and of finding a maximum uniquely restricted matching in a given graph, and present algorithms and complexity results for certain special classes of graphs. We demonstrate that testing whether a given matching M is uniquely restricted can be done in O(|M||E|) time for an arbitrary graph G=(V,E) and in linear time for cacti, interval graphs, bipartite graphs, split graphs and threshold graphs. The maximum uniquely restricted matching problem is shown to be NP-complete for bipartite graphs, split graphs, and hence for chordal graphs and comparability graphs, but can be solved in linear time for threshold graphs, proper interval graphs, cacti and block graphs. Received April 12, 1998; revised June 21, 1999.     

Greedy Geometric Algorithms for Collection of Balls,with Applications to Geometric Approximation and Molecular Coarse‐Graining

Choosing balls that best approximate a 3D object is a non‐trivial problem. To answer it, we first address the inner approximation problem, which consists of approximating an object defined by a union of n balls with balls defining a region . This solution is further used to construct an outer approximation enclosing the initial shape, and an interpolated approximation sandwiched between the inner and outer approximations. The inner approximation problem is reduced to a geometric generalization of weighted max k‐cover, solved with the greedy strategy which achieves the classical lower bound. The outer approximation is reduced to exploiting the partition of the boundary of by the Apollonius Voronoi diagram of the balls defining the inner approximation. Implementation‐wise, we present robust software incorporating the calculation of the exact Delaunay triangulation of points with degree two algebraic coordinates, of the exact medial axis of a union of balls, and of a certified estimate of the volume of a union of balls. Application‐wise, we exhibit accurate coarse‐grain molecular models using a number of balls 20 times smaller than the number of atoms, a key requirement to simulate crowded cellular environments.     

On Time-Space Efficiency of Digital Trees with Adaptive Multidigit Branching

Parameters of time-space efficiency and sparseness of nodes in trees with adaptive multidigit branching are studied. Both precise and asymptotic expressions, describing average behavior of these parameters in a memoryless model, are obtained. These expressions are used to establish a relation between parameters. As a result, conditions of time-space optimality of trees constructed with the use of Nilsson and Tikkanen algorithm are obtained.