A new constrained edit distance between quotiented ordered trees

In this paper we propose a dynamic programming algorithm to compare two quotiented ordered trees using a constrained edit distance. An ordered tree is a tree in which the left-to-right order among siblings is significant. A quotiented ordered tree is an ordered tree T with an equivalence relation on vertices and such that, when the equivalence classes are collapsed to super-nodes, the graph so obtained is an ordered tree as well. Based on an algorithm proposed by Zhang and Shasha [K. Zhang, D. Shasha, Simple fast algorithms for the editing distance between trees and related problems, SIAM Journal on Computing 18 (6) (1989) 1245–1262] and introducing new notations, we describe a tree edit distance between quotiented ordered trees preserving equivalence relations on vertices during computation which works in polynomial time. Its application to RNA secondary structures comparison is finally presented.     

Blossom V: a new implementation of a minimum cost perfect matching algorithm

We describe a new implementation of the Edmonds’s algorithm for computing a perfect matching of minimum cost, to which we refer as Blossom V. A key feature of our implementation is a combination of two ideas that were shown to be effective for this problem: the “variable dual updates” approach of Cook and Rohe (INFORMS J Comput 11(2):138–148, 1999) and the use of priority queues. We achieve this by maintaining an auxiliary graph whose nodes correspond to alternating trees in the Edmonds’s algorithm. While our use of priority queues does not improve the worst-case complexity, it appears to lead to an efficient technique. In the majority of our tests Blossom V outperformed previous implementations of Cook and Rohe (INFORMS J Comput 11(2):138–148, 1999) and Mehlhorn and Schäfer (J Algorithmics Exp (JEA) 7:4, 2002), sometimes by an order of magnitude. We also show that for large VLSI instances it is beneficial to update duals by solving a linear program, contrary to a conjecture by Cook and Rohe.     

Representation complexity of adaptive 3D distance fields

In this paper we study the representation complexity of a kind of data structure that stores the information necessary to compute the distance from a point to a geometric body. These data structures called adaptive splitting based on cubature distance fields (ASBCDF), are binary search trees generated by the adaptive splitting based on cubature (ASBC) algorithm that adaptively subdivides the space surrounding the body into tetrahedra. Their representation complexity is measured by the number of nodes in the tree (two times the number of tetrahedra in the resulting tessellation). In the case of convex polyhedra we prove that this quantity remains bounded as the number of vertices of the polyhedra increases to infinity. Experimental results show that the number of tetrahedra in the tessellations is almost independent of the combinatorial complexity of the polyhedra. This means that the average compute time of the distance to arbitrary convex polyhedra is almost constant. Therefore, ASBCDFs are especially suitable for real time applications involving rapidly changing environments modelized with complex polyhedra.     

An O(n2) simplex algorithm for a class of linear programs with tree structure

In connection with the optimal design of centralized circuit-free networks linear 0–1 programming problems arise which are related to rooted trees. For each problem the variables correspond to the edges of a given rooted tree T. Each path from a leaf to the root of T, together with edge weights, defines a linear constraint, and a global linear objective is to be maximized. We consider relaxations of such problems where the variables are not restricted to 0 or 1 but are allowed to vary continouosly between these bounds. The values of the optimal solutions of such relaxations may be used in a branch and bound procedure for the original 0–1 problem. While in [10] a primal algorithm for these relaxations is discussed, in this paper, we deal with the dual linear program and present a version of the simplex algorithm for its solution which can be implemented to run in time O(n²). For balanced trees T this time can be reduced to O(n log n).     

The square of a block graph

The square H² of a graph H is obtained from H by adding new edges between every two vertices having distance two in H. A block graph is one in which every block is a clique. For the first time, good characterizations and a linear time recognition of squares of block graphs are given in this paper. Our results generalize several previous known results on squares of trees.     

Fast computation of the modality of polygons

The modality of a vertex of a polygon is the number of minima or maxima in the distance function from the vertex under consideration to each of the other vertices taken in order around the polygon. Modality was defined by Avis, Toussaint, and Bhattacharya (Comput. Math Appl., 8 (1982), 153–156) and has been further studied by Toussaint and Bhattacharya (Technical Report, No. SOCS-81.3, School of Computer Science, McGill University, January 1981). These authors have defined modality for polygons, both convex and nonconvex, but have not given an algorithm to compute the modality of a polygon, other than the obvious algorithm derived from the definition, which is quadratic in the number of vertices of the polygon. Our paper gives a modality-determination algorithm for convex polygons whose running time is linear in the sum of the number of vertices and the total modality of the polygon. As a special case, we can test if a convex polygon is unimodal (a term introduced by Avis et al.) in time O(n) for a polygon with n vertices. This latter result is shown to be optimal to within a constant factor. We then extend our technique to nonconvex polygons and derive a modality-determination algorithm which is better than the obvious algorithm, but probably not optimal. We conclude by posing some open problems and indicating a connection between modality determination and a range query problem which has received some attention in the Computational Geometry literature.     

Recognizing and representing proper interval graphs in parallel using merging and sorting

We present a parallel algorithm for recognizing and representing a proper interval graph in time with O(m+n) processors on the CREW PRAM, where m and n are the number of edges and vertices in the graph. The algorithm uses sorting to compute a weak linear ordering of the vertices, from which an interval representation is easily obtained. It is simple, uses no complex data structures, and extends ideas from an optimal sequential algorithm for recognizing and representing a proper interval graph [X. Deng, P. Hell, J. Huang, Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs, SIAM J. Comput. 25 (2) (1996) 390-403].     

Optimal scheduling on parallel machines for a new order class

This paper addresses the problem of scheduling n unit length tasks on m identical machines under certain precedence constraints. The aim is to compute minimal length nonpreemptive schedules. We introduce a new order class which contains properly two rich families of precedence graphs: interval orders and a subclass of the class of series parallel orders. We present a linear time algorithm to find an optimal schedule for this new order class on any number of machines.     

On the Maximum Parsimony Distance Between Phylogenetic Trees

Within the field of phylogenetics there is great interest in distance measures to quantify the dissimilarity of two trees. Here, based on an idea of Bruen and Bryant, we propose and analyze a new distance measure: theMaximum Parsimony (MP) distance. This is based on the difference of the parsimony scores of a single character on both trees under consideration, and the goal is to find the character which maximizes this difference. In this article we show that this new distance is a metric and provides a lower bound to the well-known Subtree Prune and Regraft (SPR) distance. We also show that to compute the MP distance it is sufficient to consider only characters that are convex on one of the trees, and prove several additional structural properties of the distance. On the complexity side, we prove that calculating the MP distance is in general NP-hard, and identify an interesting island of tractability in which the distance can be calculated in polynomial time.     

Gröbner–Shirshov basis for the Braid group in the Birman–Ko–Lee generators

In this paper, we obtain Gröbner–Shirshov (non-commutative Gröbner) bases for braid groups in the Birman–Ko–Lee generators enriched by “Garside word” δ [J. Birman, K.H. Ko, S.J. Lee, A new approach to the word and conjugacy problems for the braid groups, Adv. Math. 139 (1998) 322–353]. It gives a new algorithm for getting the Birman–Ko–Lee normal forms in braid groups, and thus a new algorithm for solving the word problem in these groups.     

t-Pebbling and Extensions

Graph pebbling is the study of moving discrete pebbles from certain initial distributions on the vertices of a graph to various target distributions via pebbling moves. A pebbling move removes two pebbles from a vertex and places one pebble on one of its neighbors (losing the other as a toll). For t ≥ 1 the t-pebbling number of a graph is the minimum number of pebbles necessary so that from any initial distribution of them it is possible to move t pebbles to any vertex. We provide the best possible upper bound on the t-pebbling number of a diameter two graph, proving a conjecture of Curtis et al., in the process. We also give a linear time (in the number of edges) algorithm to t-pebble such graphs, as well as a quartic time (in the number of vertices) algorithm to compute the pebbling number of such graphs, improving the best known result of Bekmetjev and Cusack. Furthermore, we show that, for complete graphs, cycles, trees, and cubes, we can allow the target to be any distribution of t pebbles without increasing the corresponding t-pebbling numbers; we conjecture that this behavior holds for all graphs. Finally, we explore fractional and optimal fractional versions of pebbling, proving the fractional pebbling number conjecture of Hurlbert and using linear optimization to reveal results on the optimal fractional pebbling number of vertex-transitive graphs.     

Gérard–Levelt membranes

We present an unexpected application of tropical convexity to the determination of invariants for linear systems of differential equations. We show that the classical Gérard–Levelt lattice saturation procedure can be geometrically understood in terms of a projection on the tropical linear space attached to a subset of the local affine Bruhat–Tits building, which we call the Gérard–Levelt membrane. This provides a way to compute the true Poincaré rank, but also the Katz rank of a meromorphic connection without having to perform either gauge transforms or ramifications of the variable. We finally present an efficient algorithm to compute this tropical projection map, generalising Ardila’s method for Bergman fans to the case of the tight-span of a valuated matroid.     

Finding a Simple Polytope from Its Graph in Polynomial Time

We show that one can compute the combinatorial facets of a simple polytope from its graph in polynomial time. Our proof relies on a primal-dual characterization (by Joswig, Kaibel, and Körner in Israel J. Math. 129:109–118, 2002) and a linear program, with an exponential number of constraints, which can be used to construct the solution and can be solved in polynomial time. We show that this allows one to characterize the face lattice of the polytope, via a simple face recognition algorithm. In addition, we use this linear program to construct several interesting polynomial-time computable sets of graphs which may be of independent interest.     

Comparison of alignment free string distances for complete genome phylogeny

In this paper, we compare the accuracy of four string distances on complete genomes to reconstruct phylogenies using simulated and real biological data. These distances are based on common words shared by raw genomic sequences and do not require preliminary processing steps such as gene identification or sequence alignment. Moreover, they are computable in linear time. The first distance is based on Maximum Significant Matches (MSM). The second is computed from the frequencies of all the words of length k (KW). The third distance is based on the Average length of maximum Common Substrings at any position (ACS). The last one is based on the Ziv–Lempel compression algorithm (ZL). We describe a simulation process of evolution to generate a set of sequences having evolved according to a random tree topology T. This process allows both base substitution and fragment insertion/deletion, including horizontal transfers. The distances between the generated sequences are computed using the four formulas and the corresponding trees T′ are reconstructed using Neighbor-Joining. T and T′ are compared according to topological criteria. These comparisons show that the MSM distance outperforms the others whatever the parameters used to generate sequences. Finally, we test the MSM and KW distances on real biological data (i.e. prokaryotic complete genomes) and we compare the NJ trees to a Maximum Likelihood 16S + 23S RNA tree. We show that the MSM distance provides accurate results to study intra-phylum relationships, much better than those given by KW.     

The use of dynamic programming in genetic algorithms for permutation problems

To deal with computationally hard problems, approximate algorithms are used to provide reasonably good solutions in practical time. Genetic algorithms are an example of the meta-heuristics which were recently introduced and which have been successfully applied to a variety of problems. We propose to use dynamic programming in the process of obtaining new generation solutions in the genetic algorithm, and call it a genetic DP algorithm. To evaluate the effectiveness of this approach, we choose three representative combinatorial optimization problems, the single machine scheduling problem, the optimal linear arrangement problem and the traveling salesman problem, all of which ask to compute optimum permutations of n objects and are known to be NP-hard. Computational results for randomly generated problem instances exhibit encouraging features of genetic DP algorithms.     

L 1 C 1 polynomial spline approximation algorithms for large data sets

In this article, we address the problem of approximating data points by C ¹-smooth polynomial spline curves or surfaces using L ₁-norm. The use of this norm helps to preserve the data shape and it reduces extraneous oscillations. In our approach, we introduce a new functional which enables to control directly the distance between the data points and the resulting spline solution. The computational complexity of the minimization algorithm is nonlinear. A local minimization method using sliding windows allows to compute approximation splines within a linear complexity. This strategy seems to be more robust than a global method when applied on large data sets. When the data are noisy, we iteratively apply this method to globally smooth the solution while preserving the data shape. This method is applied to image denoising.     

A New Lower Bound for the Kirchhoff Index using a numerical procedure based on Majorization Techniques

In this note, we use a procedure, proposed in [Bianchi, M., and A. Torriero, Some localization theorems using a majorization technique, Journal of Inequalities and Applications 5 (2000), 433–446], based on a majorization technique, which localizes real eigenvalues of a matrix of order n. Through this information, we compute a lower bound for the Kirchhoff index (see [Bianchi M., A. Cornaro, J.L. Palacios and A. Torriero, Bounds for the Kirkhhoff index via majorization techniques, Journal of Mathematical Chemistry, (2012) online first]) that takes advantage of additional eigenvalues bounds. An algorithm has been developed with MATLAB software to evaluate the above mentioned bound. Finally, numerical examples are provided showing how tighter results can be obtained.     

Computing border bases

This paper presents several algorithms that compute border bases of a zero-dimensional ideal. The first relates to the FGLM algorithm as it uses a linear basis transformation. In particular, it is able to compute border bases that do not contain a reduced Gröbner basis. The second algorithm is based on a generic algorithm by Bernard Mourrain originally designed for computing an ideal basis that need not be a border basis. Our fully detailed algorithm computes a border basis of a zero-dimensional ideal from a given set of generators. To obtain concrete instructions we appeal to a degree-compatible term ordering σ and hence compute a border basis that contains the reduced σ-Gröbner basis. We show an example in which this computation actually has advantages over Buchberger's algorithm. Moreover, we formulate and prove two optimizations of the Border Basis Algorithm which reduce the dimensions of the linear algebra subproblems.     

A Newton-based method for the calculation of the distance to instability

In this paper, a new fast algorithm for the computation of the distance of a stable matrix to the unstable matrices is provided. The method uses Newton’s method to find a two-dimensional Jordan block corresponding to a pure imaginary eigenvalue in a certain two-parameter Hamiltonian eigenvalue problem introduced by Byers [R. Byers, A bisection method for measuring the distance of a stable matrix to the unstable matrices, SIAM J. Sci. Statist. Comput. 9 (1988) 875-881]. This local method is augmented by a test step, previously used by other authors, to produce a global method. Numerical results are presented for several examples and comparison is made with the methods of Boyd and Balakrishnan [S. Boyd, V. Balakrishnan, A regularity result for the singular values of a transfer matrix and a quadratically convergent algorithm for computing its L_∞-norm, Systems Control Lett. 15 (1990) 1-7] and He and Watson [C. He, G.A. Watson, An algorithm for computing the distance to instability, SIAM J. Matrix Anal. Appl. 20 (1999) 101-116].