Publications of Dekel Tsur

  1. R. Shamir and D. Tsur.
    Faster subtree isomorphism.
    J. of Algorithms, 33:267-280, 1999.
    A preleminary version appeared in Proc. 5th Israel Symposium on Theory of Computing and Systems, (ISTCS), 126-131, 1997.

  2. R. Shamir and D. Tsur.
    The maximum subforest problem: Approximation and exact algorithms.
    Proc. 9th Symposium on Discrete Algorithms (SODA), 394-399, 1998.

  3. R. Shamir and D. Tsur.
    Large scale sequencing by hybridization.
    J. of Computational Biology, 9(2):413-428, 2002.
    A preleminary version appeared in Proc. 5th International Conference on Computational Molecular Biology (RECOMB), 267-279, 2001.

  4. R. Sharan, R. Shamir, and D. Tsur.
    Cluster graph modification problems.
    Discrete Applied Math, 144:173-182, 2004.
    A preleminary version appeared in Proc. 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), LNCS 2573, 379-390, 2002.

  5. R. Shamir and D. Tsur.
    Improved algorithms for the random cluster graph model.
    Random Structures and Algorithms, 31(4):418-449, 2007.
    A preleminary version appeared in Proc. 8th Scandinavian Workshop on Algorithm Theory (SWAT), LNCS 2368, 230-239, 2002.

  6. D. Tsur.
    Bounds for resequencing by hybridization.
    Proc. 3rd Workshop on Algorithms in Bioinformatics (WABI), LNCS 2812, 498-511, 2003.

  7. D. Tsur.
    Sequencing by hybridization in few rounds.
    J. of Computer and System Sciences, 76(8):751-758, 2010.
    A preleminary version appeared in Proc. 11th European Symposium on Algorithms (ESA), LNCS 2832, 506-516, 2003.

  8. B. Awerbuch, Y. Azar, Y. Richter, and D. Tsur.
    Tradeoffs in worst-case equilibria.
    Theoretical Computer Science, 361(2-3):200-209, 2006.
    A preleminary version appeared in Proc. 1st International Workshop on Approximation and Online Algorithms (WAOA), LNCS 2909, 41-52, 2003.

  9. A. Amir, O. Kapah, and D. Tsur.
    Faster two dimensional pattern matching with rotations.
    Theoretical Computer Science, 368(3):196-204, 2006.
    A preleminary version appeared in Proc. 15th Symposium on Combinatorial Pattern Matching (CPM), LNCS 3109, 409-419, 2004.

  10. R. Y. Pinter, O. Rokhlenko, D. Tsur, and M. Ziv-Ukelson.
    Approximate labelled subtree homeomorphism.
    J. of Discrete Algorithms, 6:480-496, 2008.
    A preleminary version appeared in Proc. 15th Symposium on Combinatorial Pattern Matching (CPM), LNCS 3109, 59-73, 2004.

  11. A. Amir, A. Butman, M. Lewenstein, E. Porat, and D. Tsur.
    Efficient one dimensional real scaled matching.
    J. of Discrete Algorithms, 5(2):205-211, 2007.
    A preleminary version appeared in Proc. 11th Symposium on String Processing and Information Retrieval (SPIRE), LNCS 3246, 1-9, 2004.

  12. D. Tsur.
    Sequencing by hybridization with errors: handling longer sequences.
    Theoretical Computer Science, 332:559-566, 2005.

  13. R. Cole, C. Hazay, M. Lewenstein, and D. Tsur.
    Two dimensional parameterized matching.
    ACM Transactions on Algorithms, 11(2):12:1-12:30, 2014.
    A preleminary version appeared in Proc. 16th Symposium on Combinatorial Pattern Matching (CPM), LNCS 3537, 266-279, 2005.

  14. M. Farach-Colton, G. M. Landau, S. C. Sahinalp, and D. Tsur.
    Optimal spaced seeds for faster approximate string matching.
    J. of Computer and System Sciences, 73(7):1035-1044, 2007.
    A preleminary version appeared in Proc. 32nd International Colloquium on Automata, Languages and Programming (ICALP), LNCS 3580, 1251-1262, 2005.

  15. D. Tsur, S. Tanner, E. Zandi, V. Bafna, and P. A. Pevzner.
    Identification of post-translational modifications via blind search of mass-spectra.
    Nature Biotechnology, 23:1562-1567, 2005.
    A preleminary version appeared in Proc. 4th Computational Systems Bioinformatics Conference (CSB), 157-166, 2005.

  16. D. Tsur.
    Tight bounds for string reconstruction using substring queries.
    Proc. 9th International Workshop on Randomization and Computation (RANDOM), LNCS 3624, 448-459, 2005.

  17. N. Bandeira, A. Frank, P. A. Pevzner, and D. Tsur.
    Protein identification by spectral networks analysis.
    Proc. National Academy of Science USA, 104(15):6140-6145, 2007.
    A preleminary version appeared in Proc. 10th International Conference on Computational Molecular Biology (RECOMB), LNCS 3909, 363-378, 2006.

  18. D. Tsur.
    Optimal probing patterns for sequencing by hybridization.
    Proc. 6th Workshop on Algorithms in Bioinformatics (WABI), 366-375, 2006.

  19. G. Didier, T. Schmidt, J. Stoye, and D. Tsur.
    Character sets of strings.
    J. of Discrete Algorithms, 5(2):330-340, 2007.

  20. D. Tsur.
    Tree-edges deletion problems with bounded diameter obstruction sets.
    Discrete Applied Math, 155(10):1275-1293, 2007.

  21. Y. Aumann, M. Lewenstein, N. Lewenstein, and D. Tsur.
    Finding witnesses by peeling.
    ACM Transactions on Algorithms, 7(2):24:1-24:15, 2011.
    A preleminary version appeared in Proc. 18th Symposium on Combinatorial Pattern Matching (CPM), LNCS 4580, 28-39, 2007.

  22. D. Tsur.
    Improved scheduling in rings.
    J. Parallel and Distributed Computing, 67(5):531-535, 2007.

  23. S. Halevi, O. Lachish, I. Newman, and D. Tsur.
    Testing properties of constraint-graphs.
    Proc. 22nd Annual IEEE Conference on Computational Complexity (CCC), 264-277, 2007.

  24. A. Amir, T. Hartman, O. Kapah, R. Shalom, and D. Tsur.
    Generalized LCS.
    Theoretical Computer Science, 409(3):438-449, 2008.
    A preleminary version appeared in Proc. 14th Symposium on String Processing and Information Retrieval (SPIRE), LNCS 4726, 50-61, 2007.

  25. G. M. Landau, D. Tsur, and O. Weimann.
    Indexing a dictionary for subset matching queries.
    Algorithms and Applications: Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday, 2010.
    A preleminary version appeared in Proc. 14th Symposium on String Processing and Information Retrieval (SPIRE), LNCS 4726, 195-204, 2007.

  26. S. Mozes, D. Tsur, O. Weimann, and M. Ziv-Ukelson.
    Fast algorithms for computing tree LCS.
    Theoretical Computer Science, 410(43):4303-4314, 2009.
    A preleminary version appeared in Proc. 19th Symposium on Combinatorial Pattern Matching (CPM), LNCS 5029, 230-243, 2008.

  27. D. Tsur.
    Faster algorithms for guided tree edit distance.
    Information Processing Letters, 108(4):251-254, 2008.

  28. R. Backofen, G. M. Landau, M. Mohl, D. Tsur, and O. Weimann.
    Fast RNA structure alignment for crossing input structures.
    J. of Discrete Algorithms, 9(1):2-11, 2011.
    A preleminary version appeared in Proc. 20th Symposium on Combinatorial Pattern Matching (CPM), LNCS 5577, 236-248, 2009.

  29. R. Backofen, D. Tsur, S. Zakov, and M. Ziv-Ukelson.
    Sparse RNA folding: time and space efficient algorithms.
    J. of Discrete Algorithms, 9(1):12-31, 2011.
    A preleminary version appeared in Proc. 20th Symposium on Combinatorial Pattern Matching (CPM), LNCS 5577, 249-262, 2009.

  30. D. Tsur.
    Fast index for approximate string matching.
    J. of Discrete Algorithms, 8(4):339-345, 2010.

  31. S. Zakov, D. Tsur, and M. Ziv-Ukelson.
    Reducing the worst case running times of a family of RNA and CFG problems, using Valiant's approach.
    Algorithms for Molecular Biology, 6:20, 2011.
    A preleminary version appeared in Proc. 10th Workshop on Algorithms in Bioinformatics (WABI), 65-77, 2010.

  32. T. Pinhas, D. Tsur, S. Zakov, and M. Ziv-Ukelson.
    Efficient edit distance with duplications and contractions.
    Algorithms for Molecular Biology, 8:27, 2013.
    A preleminary version appeared in Proc. 22nd Symposium on Combinatorial Pattern Matching (CPM), 441-454, 2011.

  33. U. Matarazzo, D. Tsur, and M. Ziv-Ukelson.
    Efficient all path score computations on grid graphs.
    Theoretical Computer Science, 525:138-149, 2014.
    A preleminary version appeared in Proc. 24th Symposium on Combinatorial Pattern Matching (CPM), 211-222, 2013.

  34. D. Tsur.
    Top-k document retrieval in optimal space.
    Information Processing Letters, 113(12):440-443, 2013.

  35. G. Kucherov, K. Salikhov, and D. Tsur.
    Approximate string matching using a bidirectional index.
    Theoretical Computer Science, 638:145-158, 2016.
    A preleminary version appeared in Proc. 25th Symposium on Combinatorial Pattern Matching (CPM), 222-231, 2014.

  36. A. Carmel, N. Musa-Lempel, D. Tsur, and M. Ziv-Ukelson.
    The worst case complexity of maximum parsimony.
    J. of Computational Biology, 21(11):799-808, 2014.
    A preleminary version appeared in Proc. 25th Symposium on Combinatorial Pattern Matching (CPM), 79-88, 2014.

  37. G. Kucherov and D. Tsur.
    Improved filters for the approximate suffix-prefix overlap problem.
    Proc. 21st Symposium on String Processing and Information Retrieval (SPIRE), 139-148, 2014.

  38. D. Tsur.
    Succinct representation of labeled trees.
    Theoretical Computer Science, 562:320-329, 2015.

  39. A. Carmel, D. Tsur, and M. Ziv-Ukelson.
    On almost Monge all scores matrices.
    Algorithmica, 81(1):47-68, 2019.
    A preleminary version appeared in Proc. 27th Symposium on Combinatorial Pattern Matching (CPM), 17:1-17:12, 2016.

  40. D. Tsur.
    Succinct data structures for nearest colored node in a tree.
    Information Processing Letters, 132:6-10, 2018.

  41. D. Tsur.
    Succinct data structure for dynamic trees with faster queries.
    Theoretical Computer Science, 780:12-19, 2019.

  42. D. Tsur.
    Faster deterministic parameterized algorithm for k-Path.
    Theoretical Computer Science, 790:96-104, 2019.

  43. D. Tsur.
    The effective entropy of next/previous larger/smaller value queries.
    Information Processing Letters, 145:39-43, 2019.

  44. D. Tsur.
    Parameterized algorithm for 3-path vertex cover.
    Theoretical Computer Science, 783:1-8, 2019.

  45. D. Tsur.
    Faster parameterized algorithm for pumpkin vertex deletion set.
    Information Processing Letters, 147:74-76, 2019.

  46. D. Tsur.
    Representation of ordered trees with a given degree distribution.
    arXiv preprint arXiv:1807.00371, 2018.

  47. D. Tsur.
    Weighted vertex cover on graphs with maximum degree 3.
    arXiv preprint arXiv:1810.12982, 2018.

  48. D. Tsur.
    An O^*(2.619^k) algorithm for 4-path vertex cover.
    arXiv preprint arXiv:1811.03592, 2018.

  49. D. Tsur.
    Above guarantee parameterization for vertex cover on graphs with maximum degree 4.
    arXiv preprint arXiv:1812.10808, 2018.

  50. D. Tsur.
    Faster parameterized algorithm for Cluster Vertex Deletion.
    arXiv preprint arXiv:1901.07609, 2019.

  51. D. Tsur.
    Algorithms for deletion problems on split graphs.
    arXiv preprint arXiv:1906.10012, 2019.

  52. D. Tsur.
    l-path vertex cover is easier than l-hitting set for small l.
    arXiv preprint arXiv:1906.10523, 2019.

  53. D. Tsur.
    Cluster deletion revisited.
    arXiv preprint arXiv:1907.08399, 2019.

  54. D. Tsur.
    An FPT algorithm for orthogonal buttons and scissors.
    arXiv preprint arXiv:1907.10230, 2019.

  55. D. Tsur.
    Faster algorithms for cograph edge modification problems.
    arXiv preprint arXiv:1908.01223, 2019.

  56. D. Tsur.
    Kernel for K_t-free edge deletion.
    arXiv preprint arXiv:1908.03600, 2019.

  57. D. Tsur.
    An algorithm for destroying claws and diamonds.
    arXiv preprint arXiv:1908.07318, 2019.

  58. D. Tsur.
    Faster parameterized algorithm for Bicluter Editing.
    arXiv preprint arXiv:1910.07944, 2019.