6 papers
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…
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…