16 papers · 1 filter
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…