2 citations · 4 across the 8 of their papers we have counts for
19 papers · 1 filter
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…
Variations on the Problem of Identifying Spectrum-Preserving String Sets
Sankardeep Chakraborty, Roberto Grossi, Ren Kimura +3
In computational genomics, many analyses rely on efficient storage and traversal of -mers, motivating compact representations such as spectrum-preserving string sets (SPSS), whi…
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…
Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage
Girish Balakrishnan, Sankardeep Chakraborty, N S Narayanaswamy +1
We improve the worst-case information theoretic lower bound of Munro and Wu (ISAAC 2018) for vertex unlabeled chordal graphs when vertex leafage is bounded and leafage is unbou…
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…
Succinct Data Structure for Path Graphs
Girish Balakrishnan, Sankardeep Chakraborty, N S Narayanaswamy +1
We consider the problem of designing a succinct data structure for {\it path graphs} (which are a proper subclass of chordal graphs and a proper superclass of interval graphs) on $…
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…
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…
Space Efficient Algorithms for Breadth-Depth Search
Sankardeep Chakraborty, Anish Mukherjee, Srinivasa Rao Satti
Continuing the recent trend, in this article we design several space-efficient algorithms for two well-known graph search methods. Both these search methods share the same name {\i…
Indexing Graph Search Trees and Applications
Sankardeep Chakraborty, Kunihiko Sadakane
We consider the problem of compactly representing the Depth First Search (DFS) tree of a given undirected or directed graph having vertices and edges while supporting vario…
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…
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…
Frameworks for Designing In-place Graph Algorithms
Sankardeep Chakraborty, Anish Mukherjee, Venkatesh Raman +1
Read-only memory model is a classical model of computation to study time-space tradeoffs of algorithms. One of the classical results on the ROM model is that any sorting algorithm…
Biconnectivity, -numbering and other applications of DFS using bits
Sankardeep Chakraborty, Venkatesh Raman, Srinivasa Rao Satti
We consider space efficient implementations of some classical applications of DFS including the problem of testing biconnectivity and -edge connectivity, finding cut vertices an…
Improved Space efficient linear time algorithms for BFS, DFS and applications
Niranka Banerjee, Sankardeep Chakraborty, Venkatesh Raman +1
Recent work by Elmasry et al. (STACS 2015) and Asano et al. (ISAAC 2014), reconsidered classical fundamental graph algorithms focusing on improving the space complexity. We continu…