1 citations · 1 across the 10 of their papers we have counts for
17 papers
Optimal Labeling Schemes for -Free Matrices
Sankardeep Chakraborty, Seungbum Jo
We study labeling schemes for -free binary matrices, which do not contain a submatrix of the form . We give a label…
Succinct Representation of Search Trees on Trees
Seungbum Jo, Nodari Sitchinava
A search tree on trees (STT) is a data structure for performing a search for a target vertex in a reference tree. A standard binary search tree is a special case of an STT, where t…
Indexing Range Maximum-Sum Segment Queries with Offsets
Seungbum Jo, Dominik Köppl
Given an array of real numbers, the maximum segment sum (MSS) problem is to find a contiguous subarray that has the largest sum. While the MSS problem can be solved optimally w…
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…
Succinct Data Structures for Baxter Permutation and Related Families
Sankardeep Chakraborty, Seungbum Jo, Geunho Kim +1
A permutation is a Baxter permutation if and only if it does not contain either of the patterns and . Baxter permutations are one of the m…
A Simple Representation of Tree Covering Utilizing Balanced Parentheses and Efficient Implementation of Average-Case Optimal RMQs
Kou Hamada, Sankardeep Chakraborty, Seungbum Jo +3
Tree covering is a technique for decomposing a tree into smaller-sized trees with desirable properties, and has been employed in various succinct data structures. However, signific…
Cell-Probe Lower Bound for Accessible Interval Graphs
Sankardeep Chakraborty, Christian Engels, Seungbum Jo +1
We spot a hole in the area of succinct data structures for graph classes from a universe of size at most . Very often, the input graph is labeled by the user in an arbitrary a…
Succinct Data Structure for Graphs with -Dimensional -Representation
Girish Balakrishnan, Sankardeep Chakraborty, Seungbum Jo +2
Erdős and West (Discrete Mathematics'85) considered the class of vertex intersection graphs which have a {\em -dimensional} {\em -representation}, that is, each vertex of…
Space-efficient Data Structure for Next/Previous Larger/Smaller Value Queries
Seungbum Jo, Geunho Kim
Given an array of size from a total order, we consider the problem of constructing a data structure that supports various queries (range minimum/maximum queries with their vari…
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…
Succinct Navigational Oracles for Families of Intersection Graphs on a Circle
Hüseyin Acan, Sankardeep Chakraborty, Seungbum Jo +3
We consider the problem of designing succinct navigational oracles, i.e., succinct data structures supporting basic navigational queries such as degree, adjacency, and neighborhood…
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…
Compressed Range Minimum Queries
Paweł Gawrychowski, Seungbum Jo, Shay Mozes +1
Given a string of integers in , a range minimum query RMQ asks for the index of the smallest integer in . It is well known that the problem can…
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…
Simultaneous encodings for range and next/previous larger/smaller value queries
Seungbum Jo, Srinivasa Rao Satti
Given an array of elements from a total order, we propose encodings that support various range queries (range minimum, range maximum and their variants), and previous and next…