1.8k citations
- Tel Aviv UniversityIL42 papers
- Boston UniversityUS31 papers
- Technion – Israel Institute of TechnologyIL26 papers
- Ben-Gurion University of the NegevIL24 papers
- Hebrew University of JerusalemIL21 papers
- University of Maryland, College ParkUS20 papers
- Ariel UniversityIL19 papers
- Centre National de la Recherche ScientifiqueFR16 papers
- Harvard UniversityUS16 papers
- Weizmann Institute of ScienceIL15 papers
- Institute of Radio AstronomyUA13 papers
- Brookhaven National LaboratoryUS12 papers
29 papers · 1 filter
Incremental Edge Orientation in Forests
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul +2
For any forest it is possible to orient the edges so that no vertex in has out-degree greater than . This paper considers the incremental edge-orientation p…
Update Query Time Trade-off for dynamic Suffix Arrays
Amihood Amir, Itai Boneh
The Suffix Array SA(S) of a string S[1 ... n] is an array containing all the suffixes of S sorted by lexicographic order. The suffix array is one of the most well known indexing da…
Weighted Adaptive Coding
Aharon Fruchtman, Yoav Gross, Shmuel T. Klein +1
Huffman coding is known to be optimal, yet its dynamic version may be even more efficient in practice. A new variant of Huffman encoding has been proposed recently, that provably a…
Time-Space Tradeoffs for Finding a Long Common Substring
Stav Ben-Nun, Shay Golan, Tomasz Kociumaka +1
We consider the problem of finding, given two documents of total length , a longest string occurring as a substring of both documents. This problem, known as the Longest Common…
Graph Realizations: Maximum and Minimum Degree in Vertex Neighborhoods
Amotz Bar-Noy, Keerti Choudhary, David Peleg +1
The classical problem of degree sequence realizability asks whether or not a given sequence of positive integers is equal to the degree sequence of some -vertex undirected s…
Cartesian Tree Matching and Indexing
Sung Gwan Park, Amihood Amir, Gad M. Landau +1
We introduce a new metric of match, called Cartesian tree matching, which means that two strings match if they have the same Cartesian trees. Based on Cartesian tree matching, we d…