Faster Two Dimensional Pattern Matching with Rotations (2004)
Amihood Amir, Oren Kapah, Dekel Tsur
The most e#cient currently known algorithms for two dimensional matching with rotation have a worst case time complexity of O(n ), where the size of the text is n and the size of the pattern is m ....
Ron Shamir, Roded Sharan, Dekel Tsur
In a clustering problem one has to partition a set of elements into homogeneous and well-separated subsets. From a graph theoretic point of view, a cluster graph is a vertex-disjoint union of...
Sequencing by Hybridization in Few Rounds (2004)
Sequencing by Hybridization (SBH) is a method for reconstructing an unknown DNA string based on substring queries: Using hybridization experiments, one can determine for each string in a given set of...
Tradeoffs in Worst-Case Equilibria (2004)
Baruch Awerbuch, Yossi Azar, Yossi Richter, Dekel Tsur
We investigate the problem of routing traffic through a congested network in an environment of non-cooperative users. We use the worst-case coordination ratio suggested by Koutsoupias and...
Faster Subtree Isomorphism (2004)
We study the subtree isomorphism problem: Given trees H and G, find a subtree of G which is isomorphic to H or decide that there is no such subtree. We give an O((k / log k)n)-time algorithm for this...
Improved Algorithms for the Random Cluster Graph Model (2003)
We model noisy clustering data using random graphs: Clusters correspond to disjoint sets of vertices. Two vertices from the same set (resp., di#erent sets) share an edge with probability p (resp., r...
Bounds for Resequencing by Hybridization (2003)
We study the problem of finding the sequence of an unknown DNA fragment given the set of its k-long subsequences and a homologous sequence, namely a sequence that is similar to the target sequence....
Cluster Graph Modification Problems (2003)
Ron Shamir, Roded Sharan, Dekel Tsur
In a clustering problem one has to partition a set of elements into homogeneous and well-separated subsets. From a graph theoretic point of view, a cluster graph is a vertex-disjoint union of...
Tradeoffs in Worst-Case Equilibria (2003)
Baruch Awerbuch, Yossi Azar, Yossi Richter, Dekel Tsur
We investigate the problem of routing traffic through a congested network in an environment of non-cooperative users. We use the worst-case coordination ratio suggested by Koutsoupias and...
Improved Algorithms for the Random Cluster Graph Model (2002)
The following probabilistic process models the generation of noisy clustering data: Clusters correspond to disjoint sets of vertices in a graph. Each two vertices from the same set are connected by...
Faster Subtree Isomorphism (2002)
We study the subtree isomorphism problem: Given trees H and G, find a subtree of G which is isomorphic to H or decide that there is no such subtree. We give an O((k / log k)n)-time algorithm for this...
Faster Subtree Isomorphism (1999)
We study the subtree isomorphism problem: Given trees H and G, find a subtree of G which is isomorphic to H or decide that there is no such subtree. We give an O( k 1:5 log k n)-time algorithm for...
Faster Subtree Isomorphism (1997)
We study the subtree isomorphism problem: Given trees H and G, find a subtree of G which is isomorphic to H or decide that there is no such subtree. We give an O( k 1:5 log k n)- time algorithm for...
The maximum subforest problem: Approximation and exact algorithms (Extended Abstract) (1970)
We study the maximum subforest problem: Given a tree G and a set of trees H, find a subgraph G'of G such that G' does not contain a subtree isomorphic to a tree from H, and the number of edges in G'...
Protein identification by spectral networks analysis
Bandeira, Nuno, Tsur, Dekel, Frank, Ari, Pevzner, Pavel A.
Advances in tandem mass spectrometry (MS/MS) steadily increase the rate of generation of MS/MS spectra. As a result, the existing approaches that compare spectra against databases are already facing...