Search

Abstract: Let denote the symmetric group on and the stabilizer subgroup of . We derive algorithms for computing Fourier transforms of left and right -invariant signals that require a total of additions and scalar multiplications. Furthermore we show that the convolution of such signals can also be computed in time linear in . [Copyright &y& Elsevier]

Abstract: By definition, a P2-graph is an undirected graph in which every vertex is contained in a path of length two. For such a graph, denotes the minimum number of paths of length two that cover all vertices of . We prove that and show that these upper and lower bounds are tight. Furthermore we show that every connected P2-graph contains a spanning tree such that . We present a linear time algorithm that produces optimal 2-path covers for trees. This is contrasted by the result that the decision problem is -complete for trivalent graphs. This graph theoretical problem originates from the task of searching a large database of biological molecules such as the Protein Data Bank (PDB) by content. [Copyright &y& Elsevier]

Abstract: In this paper we present approximate algorithms for matching two polygonal curves with respect to the Fréchet distance. We define a discrete version of the Fréchet distance as a distance measure between polygonal curves and show that this discrete version is bounded by the continuous version of the Fréchet distance. For the task of matching with respect to the discrete Fréchet distance, we develop an algorithm that is based on intersecting certain subsets of the transformation group under consideration. Our algorithm for matching two point sequences of lengths m and n under the group of rigid motions has a time complexity of for matching under the discrete Fréchet distance and can be modified for matching subcurves, closed curves and finding longest common subcurves. Group theoretical considerations allow us to eliminate translation components of affine transformations and to consider matching under arbitrary linear algebraic groups. [Copyright &y& Elsevier]