375 citations · 375 across the 7 of their papers we have counts for
13 papers
Encodings for Range Minimum Queries over Bounded Alphabets
Seungbum Jo, Srinivasa Rao Satti
Range minimum queries (RMQs) are fundamental operations with widespread applications in database management, text indexing and computational biology. While many space-efficient dat…
Space-Efficient FPT Algorithms
Arindam Biswas, Venkatesh Raman, Srinivasa Rao Satti +1
We prove algorithmic results showing that a number of natural parameterized problems are in the restricted-space parameterized classes Para-L and FPT+XL. The first class comprises…
Succinct Data Structures for Series-Parallel, Block-Cactus and 3-Leaf Power Graphs
Sankardeep Chakraborty, Seungbum Jo, Kunihiko Sadakane +1
We design succinct encodings of {\it series-parallel, block-cactus} and {\it 3-leaf power} graphs while supporting the basic navigational queries such as degree, adjacency and neig…
Enumerating Range Modes
Kentaro Sumigawa, Sankardeep Chakraborty, Kunihiko Sadakane +1
We consider the range mode problem where given a sequence and a query range in it, we want to find items with maximum frequency in the range. We give time- and space- efficient alg…
Optimal In-place Algorithms for Basic Graph Problems
Sankardeep Chakraborty, Kunihiko Sadakane, Srinivasa Rao Satti
We present linear time {\it in-place} algorithms for several basic and fundamental graph problems including the well-known graph search methods (like depth-first search, breadth-fi…
Succinct Data Structures for Families of Interval Graphs
Hüseyin Acan, Sankardeep Chakraborty, Seungbum Jo +1
We consider the problem of designing succinct data structures for interval graphs with vertices while supporting degree, adjacency, neighborhood and shortest path queries in op…
Approximate Query Processing over Static Sets and Sliding Windows
Ran Ben Basat, Seungbum Jo, Srinivasa Rao Satti +1
Indexing of static and dynamic sets is fundamental to a large set of applications such as information retrieval and caching. Denoting the characteristic vector of the set by B, we…
Encoding two-dimensional range top-k queries
Seungbum Jo, Srinivasa Rao Satti
We consider the problem of encoding two-dimensional arrays, whose elements come from a total order, for answering \topk{} queries. The aim is to obtain encodings that use space clo…
Improved Space-efficient Linear Time Algorithms for Some Classical Graph Problems
Sankardeep Chakraborty, Seungbum Jo, Srinivasa Rao Satti
This short note provides space-efficient linear time algorithms for computing bridges, topological sorting, and strongly connected components improving on several recent results of…
Synergistic Sorting, MultiSelection and Deferred Data Structures on MultiSets
Jérémy Barbay, Carlos Ochoa, Srinivasa Rao Satti
Karp et al. (1988) described Deferred Data Structures for Multisets as "lazy" data structures which partially sort data to support online rank and select queries, with the minimum…
On Succinct Representations of Binary Trees
Pooya Davoodi, Rajeev Raman, Srinivasa Rao Satti
We observe that a standard transformation between \emph{ordinal} trees (arbitrary rooted trees with ordered children) and binary trees leads to interesting succinct binary tree rep…
Random Access to Grammar Compressed Strings
Philip Bille, Gad M. Landau, Rajeev Raman +3
Grammar based compression, where one replaces a long string by a small context-free grammar that generates the string, is a simple and powerful paradigm that captures many popular…
Succinct Indexable Dictionaries with Applications to Encoding -ary Trees, Prefix Sums and Multisets
Rajeev Raman, Venkatesh Raman, Srinivasa Rao Satti
We consider the {\it indexable dictionary} problem, which consists of storing a set for some integer , while supporting the operations of $\Rank(x)$,…