Publications

• "Near Linear Time Construction of an Approximate Index for all Maximum Consecutive Sub-sums of a Sequence". Ferdinando Cicalese, Eduardo Laber, Oren Weimann, Raphael Yuster.
  • In Proceedings of the 23rd annual symposium on Combinatorial Pattern Matching (CPM 2012).

• "On Approximating String Selection Problems with Outliers". Christina Boucher, Gad M. Landau, Avivit Levy, David Pritchard, Oren Weimann.
  • In Proceedings of the 23rd annual symposium on Combinatorial Pattern Matching (CPM 2012).

• "Approximating the Diameter of Planar Graphs in Near Linear Time". Oren Weimann, Raphael Yuster.
  • In arXiv:1112.1116, December 2011.

• "Optimal Packed String Matching". Oren Ben-Kiki, Philip Bille, Danny Breslauer, Roberteo Grossi, Oren Weimann.
  • In Proceedings of the 31st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Slides

• "Distance Oracles for Vertex-Labeled Graphs". Danny Hermelin, Avivit Levy, Oren Weimann, Raphael Yuster.
  • In Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011). Slides

• "A Note on Exact Distance Labeling". David Peleg, Oren Weimann.
  • In Information Processing Letters (IPL), 111(14), 2011.

• "Random Access to Grammar-Compressed Strings". Philip Bille, Gad M. Landau, Rajeev Raman, Srinivasa Rao, Kunihiko Sadakane, Oren Weimann.
  • In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011). Slides

• "Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication". Oren Weimann, Raphael Yuster.
  • In ACM Transactions on Algorithms (TALG). To appear.
  • Preliminary version in Proceedings of the 51st Annual Symposium on Foundations Of Computer Science (FOCS 2010). Slides

• "Shortest Paths in Directed Planar Graphs with Negative Lengths: a Linear-Space O(n log²n)-Time Algorithm". Philip Klein, Shay Mozes, Oren Weimann.
  • In ACM Transactions on Algorithms (TALG), 6(2), 2010, special issue for SODA'09.
  • Preliminary version in Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009). Slides

• "Computing the Girth of a Planar Graph in O(n log n) time". Oren Weimann, Raphael Yuster.
  • In SIAM Journal on Discrete Mathematics (SIDMA), 24(2), 2010.
  • Preliminary version in Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009). Slides

• "On Cartesian Trees and Range Minimum Queries". Erik Demaine, Gad M. Landau, Oren Weimann.
  • In Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009). Slides

• "The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs". Jean Cardinal, Erik Demaine, Samuel Fiorini, Gwenaël Joret, Ilan Newman, Oren Weimann.
  • In Journal of Combinatorial Optimization (JOCO), To appear.
  • Preliminary version in Proceedings of the 5th Workshop on Internet and Network Economics (WINE 2009). Slides

• "Unified Compression-Based Acceleration of Edit-Distance Computation". Danny Hermelin, Gad M. Landau, Shir Landau, Oren Weimann.
  • In Algorithmica, To appear.
  • Preliminary version in Proceedings of the 26th international Symposium on Theoretical Aspects of Computer Science (STACS 2009). Slides

• "Fast RNA Structure Alignment for Crossing Input Structures". Rolf Backofen, Gad M. Landau, Mathias Möhl, Dekel Tsur, Oren Weimann.
  • In Journal of Discrete Algorithms (JDA), 9(1), 2011, special issue for CPM'09.
  • Preliminary version in Proceedings of the 20th annual symposium on Combinatorial Pattern Matching (CPM 2009). Slides

• "Finding an Optimal Tree Searching Strategy in Linear Time". Shay Mozes, Krzysztof Onak, Oren Weimann.
  • In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008). Slides

• "Fast Algorithms for Computing Tree LCS". Shay Mozes, Dekel Tsur, Oren Weimann, Michal Ziv-Ukelson.
  • In Theoretical Computer Science (TCS), 410(43), 2009.
  • Preliminary version in Proceedings of the 19th annual symposium on Combinatorial Pattern Matching (CPM 2008). Slides

• "An Optimal Decomposition Algorithm for Tree Edit Distance". Erik Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann.
  • In ACM Transactions on Algorithms (TALG), 6(1), 2009.
  • Preliminary version in Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007). Slides, Implementation

• "The Stackelberg Minimum Spanning Tree Game". Jean Cardinal, Erik Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann.
  • In Algorithmica, 59(2), 2011.
  • Preliminary version in Proceedings of the 10th international Workshop on Algorithms and Data Structures (WADS 2007). Slides

• "Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions". Yury Lifshit, Shay Mozes, Oren Weimann, Michal Ziv-Ukelson.
  • In Algorithmica, 54(3), 2009.
  • Preliminary version in Proceedings of the 18th annual symposium on Combinatorial Pattern Matching (CPM 2007). Slides, Implementation
  * Winner of the best paper award in CPM 2007

• "Indexing a Dictionary for Subset Matching Queries". Gad M. Landau, Dekel Tsu, Oren Weimann.
  • In Algorithms and Applications: Esko Ukkonen Festschrift, Lecture Notes in Computer Science 6060 Springer, 2010.
  • Preliminary versions in Proceedings of the 14th annual symposium on String Processing and Information Retrieval (SPIRE 2007). Slides

• "Locality and Gaps in RNA Comparison". Rolf Backofen, Shihyen Chen, Danny Hermelin, Gad M. Landau, Oren Weimann, Kaizhong Zhang.
  • In Journal of Computational Biology (JCB), 14(8), 2007.
  • Preliminary versions in Proceedings of the 17th annual symposium on Combinatorial Pattern Matching (CPM 2006) and in Proceedings of the 12th annual symposium on String Processing and Information Retrieval (SPIRE 2005). Slides

• "Gene Proximity Analysis Across Whole Genomes via PQ Trees". Gad M. Landau, Laxmi Parida, Oren Weimann.
  • In Journal of Computational Biology (JCB), 12(10), 2005.
  • Preliminary version in Proceedings of the 16th annual symposium on Combinatorial Pattern Matching (CPM 2005). Slides, Implementation