Source author record

Seungbum Jo

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

Research overview

2works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Succinct Data Structures for Families of Interval Graphs

We consider the problem of designing succinct data structures for interval graphs with $n$ vertices while supporting degree, adjacency, neighborhood and shortest path queries in optimal time in the $Θ(\log n)$ -bit word RAM model. The degree query reports the number of incident edges to a given vertex in constant time, the adjacency query returns true if there is an edge between two vertices in constant time, the neighborhood query reports the set of all adjacent vertices in time proportional to the degree of the queried vertex, and the shortest path query returns a shortest path in time proportional to its length, thus the running times of these queries are optimal. Towards showing succinctness, we first show that at least $n\log{n} - 2n\log\log n - O(n)$ bits are necessary to represent any unlabeled interval graph $G$ with $n$ vertices, answering an open problem of Yang and Pippenger [Proc. Amer. Math. Soc. 2017]. This is augmented by a data structure of size $n\log{n} +O(n)$ bits while supporting not only the aforementioned queries optimally but also capable of executing various combinatorial algorithms (like proper coloring, maximum independent set etc.) on the input interval graph efficiently. Finally, we extend our ideas to other variants of interval graphs, for example, proper/unit interval graphs, k-proper and k-improper interval graphs, and circular-arc graphs, and design succinct/compact data structures for these graph classes as well along with supporting queries on them efficiently.

preprint2016arXiv

Simultaneous encodings for range and next/previous larger/smaller value queries

Given an array of $n$ elements from a total order, we propose encodings that support various range queries (range minimum, range maximum and their variants), and previous and next smaller/larger value queries. When query time is not of concern, we obtain a $4.088n + o(n)$ -bit encoding that supports all these queries. For the case when we need to support all these queries in constant time, we give an encoding that takes $4.585n + o(n)$ bits, where $n$ is the length of input array. This improves the $5.08n+o(n)$ -bit encoding obtained by encoding the colored $2d$ -Min and Max heaps proposed by Fischer~[TCS, 2011]. We first extend the original DFUDS [Algorithmica, 2005] encoding of the colored 2d-Min (Max) heap that supports the queries in constant time. Then, we combine the extended DFUDS of $2d$ -Min heap and $2d$ -Max heap using the Min-Max encoding of Gawrychowski and Nicholson [ICALP, 2015] with some modifications. We also obtain encodings that take lesser space and support a subset of these queries.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.