Browsing by Author "cfd2e099-1189-4472-80a8-34750d8f7ba0"

Now showing items 1-6 of 6

    • Compressed Dynamic Range Majority and Minority Data Structures 
      Gagie, Travis; He, Meng; Navarro, Gonzalo (Springer, 2020)
      In the range alpha-majority query problem, we are given a sequence S[1 horizontal ellipsis n] and a fixed threshold alpha is an element of(0,1), and are asked to preprocess S such that, given a query range [i horizontal ...
    • Compressed Dynamic Range Majority Data Structures 
      Gagie, Travis; He, Meng; Navarro, Gonzalo (Institute of Electrical and Electronics Engineers Inc., 2017)
      In the range α-majority query problem, we preprocess a given sequence S[1.n] for a fixed threshold α ϵ (0, 1], such that given a query range [i.j], the symbols that occur more than α (j-i+1) times in S[i.j] can be reported ...
    • Fast and compact planar embeddings 
      Ferres, Leo; Fuentes, José; Gagie, Travis; He, Meng; Navarro, Gonzalo (Springer, 2017)
      There are many representations of planar graphs but few are as elegant as Turán’s (1984): it is simple and practical, uses only four bits per edge, can handle multi-edges and can store any specified embedding. Its main ...
    • Fast and compact planar embeddings 
      Ferres, Leo; Fuentes Sepúlveda, José; Gagie, Travis; He, Meng; Navarro, Gonzalo (Elsevier, 2020)
      There are many representations of planar graphs, but few are as elegant as Turan's (1984): it is simple and practical, uses only 4 bits per edge, can handle self-loops and multiedges, and can store any specified embedding. ...
    • Path queries on functions 
      Gagie, Travis; He, Meng; Navarro, Gonzalo (Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017)
      Let f: [1.n] → [1.n] be a function, and i: [1.n] → [1.σ] indicate a label assigned to each element of the domain. We design several compact data structures that answer various queries on the labels of paths in f. For ...
    • Tree path majority data structures 
      Gagie, Travis; He, Meng; Navarro, Gonzalo (Elsevier, 2020)
      We present the first solution to finding tau-majorities on tree paths. Given a tree of nnodes, each with a label from [1..sigma], and a fixed threshold 0 < tau 1, such a query gives two nodes u nd v nd asks for all the ...