Author name cluster

M. Farach

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

I&C Journal 1995 Journal Article

Efficient 2-Dimensional Approximate Matching of Half-Rectangular Figures

A. Amir
M. Farach

Efficient algorithms exist for the approximate two dimensional matching problem for rectangles. This is the problem of finding all occurrences of an m × m pattern in an n × n text with no more than k mismatch, insertion, and deletion errors. In computer vision it is important to generalize this problem to non-rectangular figures. We make progress towards this goal by defining half-rectangular figures of height m and area a. The approximate two dimensional matching problem for half-rectangular patterns can be solved using a dynamic programming approach in time O(an 2). We show an O(kn 2[formula][formula] + k 2 n 2) algorithm which combines convolutions with dynamic programming. Note that our algorithm is superior to previous known solutions for k ≤ m 1 3. At the heart of the algorithm are the Smaller Matching Problem and the k-Aligned Ones with Location Problem. These are interesting problems in their own right. Efficient algorithms to solve both these problems are presented.

Details DOI

I&C Journal 1995 Journal Article

Fast Comparison of Evolutionary Trees

M. Farach
M. Thorup

Constructing evolutionary trees for species sets is a fundamental problem in biology. Unfortunately, there is no single agreed upon method for this task, and many methods are in use. Current practice dictates that trees be constructed using different methods and that the resulting trees then be compared for consensus. It has become necessary to automate this process as the number of species under consideration has grown. We study the Unrooted Maximum Agreement Subtree Problem (UMAST) and its rooted variant (RMAST). The UMAST problem is as follows: given a set A and two trees T 0 and T 1 leaf-labeled by the elements of A, find a maximum cardinality subset B of A such that the restrictions of T 0 and T 1 to B are topologically isomorphic. Our main result is an O(n 2 + o(1)) time algorithm for the UMAST problem. We also derive an O(n 2) time algorithm for the RMAST problem. The previous best algorithm for both these problems has running time O(n 4. 5 + o(1)).

Details DOI

I&C Journal 1995 Journal Article

Improved Dynamic Dictionary Matching

A. Amir
M. Farach
R.M. Idury
J.A. Lapoutre
A.A. Schaffer

In the dynamic dictionary matching problem, a dictionary D contains a set of patterns that can change over time by insertion and deletion of individual patterns. The user also presents text strings and asks for all occurrences of any patterns in the text. The two main contributions of this paper are: (1) a faster algorithm for dynamic string dictionary matching with bounded alphabets, and (2) a dynamic dictionary matching algorithm for two-dimensional texts and patterns. The first contribution is based on an algorithm that solves the general problem of maintaining a sequence of well-balanced parentheses under the operations insert, delete, and find nearest enclosing parenthesis pair. The main new idea behind the second contribution is a novel method to efficiently manipulate failure links for two-dimensional patterns.

Details DOI