On exact solutions to the Euclidean bottleneck Steiner tree problem

We study the Euclidean bottleneck Steiner tree problem: given a set P of n points in the Euclidean plane and a positive integer k, find a Steiner tree with at most k Steiner points such that the length of the longest edge in the tree is minimized. This problem is known to be NP-hard even to approximate within ratio and there was no known exact algorithm even for k=1 prior to this work. In this paper, we focus on finding exact solutions to the problem for a small constant k. Based on geometric properties of optimal location of Steiner points, we present an optimal -time exact algorithm for k=1 and an O(n²)-time algorithm for k=2. Also, we present an optimal -time exact algorithm for any constant k for a special case where there is no edge between Steiner points.     

A note on exact distance labeling

We show that the vertices of an edge-weighted undirected graph can be labeled with labels of size O(n) such that the exact distance between any two vertices can be inferred from their labels alone in time. This improves the previous best exact distance labeling scheme that also requires O(n)-sized labels but time to compute the distance. Our scheme is almost optimal as exact distance labeling is known to require labels of length Ω(n).     

The use of Sherman-Morrison formula in the solution of Fredholm integral equation of second kind

We consider a constructive method for the solution of Fredholm integral equations of second kind. This method is based on a simple generalization of the well-known Sherman-Morrison formula to the infinite dimensional case. In particular, this method constructs a sequence of functions, that converges to the exact solution of the integral equation under consideration. A formal proof of this convergence result is provided for the case of Fredholm integral equations with integral kernel. Finally, a boundary value problem for the Laplace equation is considered as an example of the application of the proposed method.     

A vector similarity measure for linguistic approximation: Interval type-2 and type-1 fuzzy sets

Fuzzy logic is frequently used in computing with words (CWW). When input words to a CWW engine are modeled by interval type-2 fuzzy sets (IT2 FSs), the CWW engine’s output can also be an IT2 FS, , which needs to be mapped to a linguistic label so that it can be understood. Because each linguistic label is represented by an IT2 FS , there is a need to compare the similarity of and to find the most similar to . In this paper, a vector similarity measure (VSM) is proposed for IT2 FSs, whose two elements measure the similarity in shape and proximity, respectively. A comparative study shows that the VSM gives more reasonable results than all other existing similarity measures for IT2 FSs for the linguistic approximation problem. Additionally, the VSM can also be used for type-1 FSs, which are special cases of IT2 FSs when all uncertainty disappears.     

Comparison between a measurement error model and a linear model without measurement error

The regression of a response variable on an explanatory variable from observations on , where is a measurement of , is a special case of errors-in-variables model or measurement error model (MEM). In this work we attempt to answer the following question: given the data under a MEM, is it possible to not consider the measurement error on the covariable in order to use a simpler model? To the best of our knowledge, this problem has not been treated in the Bayesian literature. To answer that question, we compute Bayes factors, the deviance information criterion and the posterior mean of the logarithmic discrepancy. We apply these Bayesian model comparison criteria to two real data sets obtaining interesting results. We conclude that, in order to simplify the MEM, model comparison criteria can be useful to compare structural MEM and a random effect model, but we would also need other statistic tools and take into account the final goal of the model.     

On the complexity of digraph packings

Let be a fixed collection of digraphs. Given a digraph H, a -packing of H is a collection of vertex disjoint subgraphs of H, each isomorphic to a member of . For undirected graphs, Loebl and Poljak have completely characterized the complexity of deciding the existence of a perfect -packing, in the case that consists of two graphs one of which is a single edge on two vertices. We characterize -packing where consists of two digraphs one of which is a single arc on two vertices.     

The approximate swap and mismatch edit distance

There is no known algorithm that solves the general case of the approximate edit distance problem, where the edit operations are insertion, deletion, mismatch, and swap, in time o(nm), where n is the length of the text and m is the length of the pattern.In the effort to study this problem, the edit operations have been analyzed independently. Karloff [10] showed an algorithm that approximates the edit distance problem with only the mismatch operation in time . Amir et al. [4] showed that if the only edit operations allowed are swap and mismatch, then the exact edit distance problem can be solved in time .In this paper, we discuss the problem of approximate edit distance with swap and mismatch. We show a randomized time algorithm for the problem. The algorithm guarantees an approximation factor of (1+?) with probability of at least .