The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs (2009)
Cardinal, Jean, Demaine, Erik D., Fiorini, Samuel, Joret, Gwenaël, Newman, Ilan, Weimann, Oren
The Stackelberg Minimum Spanning Tree Game is a two-level combinatorial pricing problem introduced at WADS'07. The game is played on a graph (representing a network), whose edges are colored either...
Fast Algorithms for Computing Tree LCS (2009)
Shay Mozes, Dekel Tsur, Oren Weimann, Michal Ziv-ukelson
The LCS of two rooted, ordered, and labeled trees F and G is the largest forest that can be obtained from both trees by deleting nodes. We present algorithms for computing tree LCS which exploit the...
Speeding up HMM decoding and training by exploiting sequence repetitions (2009)
Lifshits, Yury, Mozes, Shay, Weimann, Oren, Ziv-Ukelson, Michal
We present a method to speed up the dynamic program algorithms used for solving the HMM decoding and training problems for discrete time-independent HMMs. We discuss the application of our method to...
A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression (2009)
Hermelin, Danny, Landau, Gad M., Landau, Shir, Weimann, Oren
We present a unified framework for accelerating edit-distance computation between two compressible strings using straight-line programs. For two strings of total length $N$ having straight-line...
A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression (2009)
Hermelin, Danny, Landau, Gad M., Landau, Shir, Weimann, Oren
We present a unified framework for accelerating edit-distance computation between two compressible strings using straight-line programs. For two strings of total length $N$ having straight-line...
A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression (2009)
Hermelin, Danny, Landau, Gad M., Landau, Shir, Weimann, Oren
We present a unified framework for accelerating edit-distance computation between two compressible strings using straight-line programs. For two strings of total length $N$ having straight-line...
A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression (2009)
Hermelin, Danny, Landau, Gad M., Landau, Shir, Weimann, Oren
The edit distance problem is a classical fundamental problem in computer science in general, and in combinatorial pattern matching in particular. The standard dynamic-programming solution for this...
Finding an Optimal Tree Searching Strategy in Linear Time (2008)
Abstract We address the extension of the binary search techniquefrom sorted arrays and totally ordered sets to trees and tree-like partially ordered sets. As in the sortedarray case, the goal is to...
Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions ⋆ (2008)
Yury Lifshits, Shay Mozes, Oren Weimann, Michal Ziv-ukelson
Abstract. We present a method to speed up the dynamic program algorithms used for solving the HMM decoding and training problems for discrete time-independent HMMs. We discuss the application of our...
Indexing a Dictionary for Subset Matching Queries (2008)
Gad M. L, Dekel Tsur, Oren Weimann
Abstract. We consider a subset matching variant of the Dictionary Query paradigm. Consider a dictionary D of n strings, where each string location contains a set of characters drawn from some...
Local Alignment of RNA Sequences with Arbitrary Scoring Schemes (2008)
Rolf Backofen, Danny Hermelin, Gad M. L, Oren Weimann
Abstract. Local similarity is an important tool in comparative analysis of biological sequences, and is therefore well studied. In particular, the Smith-Waterman technique and its normalized version...
The Stackelberg Minimum Spanning Tree Game (2007)
Cardinal, Jean, Demaine, Erik D., Fiorini, Samuel, Joret, Gwenaël, Langerman, Stefan, Newman, Ilan, ...
We consider a one-round two-player network pricing game, the {\em Stackelberg Minimum Spanning Tree} game or StackMST. The game is played on a graph (representing a network), whose edges are colored...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
Speeding up HMM decoding and training by exploiting sequence repetitions (2007)
Shay Mozes, Oren Weimann, Michal Ziv-ukelson
Abstract. We present a method to speed up the dynamic program algorithms used for solving the HMM decoding and training problems for discrete time-independent HMMs. We discuss the application of our...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Stefan Langerman, Ilan Newman, Oren Weimann
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
An optimal decomposition algorithm for tree edit distance (2007)
Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann
Abstract. The edit distance between two ordered rooted trees with vertex labels is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of...
An optimal decomposition algorithm for tree edit distance (2007)
Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann
Abstract. The edit distance between two ordered rooted trees with vertex labels is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of...
Speeding up HMM decoding and training by exploiting sequence repetitions (2007)
Shay Mozes, Oren Weimann, Michal Ziv-ukelson
Abstract. We present a method to speed up the dynamic program algorithms used for solving the HMM decoding and training problems for discrete time-independent HMMs. We discuss the application of our...
An optimal decomposition algorithm for tree edit distance (2007)
Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann
Abstract. The edit distance between two ordered rooted trees with vertex labels is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of...
An optimal decomposition algorithm for tree edit distance (2007)
Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann
Abstract. The edit distance between two ordered rooted trees with vertex labels is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
An O(n^3)-Time Algorithm for Tree Edit Distance (2006)
Demaine, Erik D., Mozes, Shay, Rossman, Benjamin, Weimann, Oren
The {\em edit distance} between two ordered trees with vertex labels is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and...
Gene proximity analysis across whole genomes via PQ trees (2005)
Gad M. Landau, Laxmi Parida, Oren Weimann
Permutations on strings representing gene clusters on genomes have been studied earlier