6 Search Results for "Chakraborty, Sankardeep"

Document
DOI: 10.4230/LIPIcs.SWAT.2024.4
Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage

Authors: Girish Balakrishnan, Sankardeep Chakraborty, N. S. Narayanaswamy, and Kunihiko Sadakane

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
Chordal graphs is a well-studied large graph class that is also a strict super-class of path graphs. Munro and Wu (ISAAC 2018) have given an (n²/4+o(n²))-bit succinct representation for n-vertex unlabeled chordal graphs. A chordal graph G = (V,E) is the intersection graph of sub-trees of a tree T. Based on this characterization, the two parameters of chordal graphs which we consider in this work are leafage, introduced by Lin, McKee and West (Discussiones Mathematicae Graph Theory 1998) and vertex leafage, introduced by Chaplick and Stacho (Discret. Appl. Math. 2014). Leafage is the minimum number of leaves in any possible tree T characterizing G. Let L(u) denote the number of leaves of the sub-tree in T corresponding to u ∈ V and k = max_{u ∈ V} L(u). The smallest k for which there exists a tree T for G is called its vertex leafage. In this work, we improve the worst-case information theoretic lower bound of Munro and Wu (ISAAC 2018) for n-vertex unlabeled chordal graphs when vertex leafage is bounded and leafage is unbounded. The class of unlabeled k-vertex leafage chordal graphs that consists of all chordal graphs with vertex leafage at most k and unbounded leafage, denoted 𝒢_k, is introduced for the first time. For k > 0 in o(n^c), c > 0, we obtain a lower bound of ((k-1)n log n -kn log k - O(log n))-bits on the size of any data structure that encodes a graph in 𝒢_k. Further, for every k-vertex leafage chordal graph G and k > 1 in o(n^c), c > 0, we present a ((k-1)n log n + o(kn log n))-bit succinct data structure, constructed using the succinct data structure for path graphs with (k-1)n vertices. Our data structure supports adjacency query in O(k log n) time and using additional 2n log n bits, an O(k² d_v log n + log² n) time neighbourhood query where d_v is degree of v ∈ V.
Cite as

Girish Balakrishnan, Sankardeep Chakraborty, N. S. Narayanaswamy, and Kunihiko Sadakane. Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{balakrishnan_et_al:LIPIcs.SWAT.2024.4,
  author =	{Balakrishnan, Girish and Chakraborty, Sankardeep and Narayanaswamy, N. S. and Sadakane, Kunihiko},
  title =	{{Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.4},
  URN =		{urn:nbn:de:0030-drops-200446},
  doi =		{10.4230/LIPIcs.SWAT.2024.4},
  annote =	{Keywords: succinct data structure, chordal graphs, leafage, vertex leafage, path graphs}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.33
Space-Efficient Data Structure for Posets with Applications

Authors: Tatsuya Yanagita, Sankardeep Chakraborty, Kunihiko Sadakane, and Srinivasa Rao Satti

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
Space efficient data structures for partial ordered sets or posets are well-researched field. It is known that a poset with n elements can be represented in n²/4 + o(n²) bits [Munro and Nicholson, 2016] and can also be represented in (1 + ε)n log n + 2nk + o(nk) bits [Farzan and Fischer, 2011] where k is width of the poset. In this paper, we make the latter data structure occupy 2n(k-1) + o(nk) bits by considering topological labeling on the elements of posets. Also considering the topological labeling, we propose a new data structure that calculates queries on transitive reduction graphs of posets faster though queries on transitive closure graphs are computed slower. Moreover, we propose an alternative data structure for topological labeled posets that calculates both of the queries faster though it uses 3nk - 2n + o(nk) bits of space. Additionally, we discuss the advantage of these data structures from the perspective of an application for BlockDAG, which is a more scalable version of Blockchain.
Cite as

Tatsuya Yanagita, Sankardeep Chakraborty, Kunihiko Sadakane, and Srinivasa Rao Satti. Space-Efficient Data Structure for Posets with Applications. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{yanagita_et_al:LIPIcs.SWAT.2022.33,
  author =	{Yanagita, Tatsuya and Chakraborty, Sankardeep and Sadakane, Kunihiko and Satti, Srinivasa Rao},
  title =	{{Space-Efficient Data Structure for Posets with Applications}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.33},
  URN =		{urn:nbn:de:0030-drops-161931},
  doi =		{10.4230/LIPIcs.SWAT.2022.33},
  annote =	{Keywords: Succinct Data Structures, Posets, Blockchain}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.29
Enumerating Range Modes

Authors: Kentaro Sumigawa, Sankardeep Chakraborty, Kunihiko Sadakane, and Srinivasa Rao Satti

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
Given a sequence of elements, we consider the problem of indexing the sequence to support range mode queries - given a query range, find the element with maximum frequency in the range. We give indexing data structures for this problem; given a sequence, we construct a data structure that can be used later to process arbitrary queries. Our algorithms are efficient for small maximum frequency cases. We also consider a natural generalization of the problem: the range mode enumeration problem, for which there has been no known efficient algorithms. Our algorithms have query time complexities which are linear in the output size plus small terms.
Cite as

Kentaro Sumigawa, Sankardeep Chakraborty, Kunihiko Sadakane, and Srinivasa Rao Satti. Enumerating Range Modes. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{sumigawa_et_al:LIPIcs.ISAAC.2020.29,
  author =	{Sumigawa, Kentaro and Chakraborty, Sankardeep and Sadakane, Kunihiko and Satti, Srinivasa Rao},
  title =	{{Enumerating Range Modes}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.29},
  URN =		{urn:nbn:de:0030-drops-133732},
  doi =		{10.4230/LIPIcs.ISAAC.2020.29},
  annote =	{Keywords: range mode, space-efficient data structure, enumeration algorithm}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.67
Indexing Graph Search Trees and Applications

Authors: Sankardeep Chakraborty and Kunihiko Sadakane

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
We consider the problem of compactly representing the Depth First Search (DFS) tree of a given undirected or directed graph having n vertices and m edges while supporting various DFS related queries efficiently in the RAM with logarithmic word size. We study this problem in two well-known models: indexing and encoding models. While most of these queries can be supported easily in constant time using O(n lg n) bits of extra space, our goal here is, more specifically, to beat this trivial O(n lg n) bit space bound, yet not compromise too much on the running time of these queries. In the indexing model, the space bound of our solution involves the quantity m, hence, we obtain different bounds for sparse and dense graphs respectively. In the encoding model, we first give a space lower bound, followed by an almost optimal data structure with extremely fast query time. Central to our algorithm is a partitioning of the DFS tree into connected subtrees, and a compact way to store these connections. Finally, we also apply these techniques to compactly index the shortest path structure, biconnectivity structures among others.
Cite as

Sankardeep Chakraborty and Kunihiko Sadakane. Indexing Graph Search Trees and Applications. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.MFCS.2019.67,
  author =	{Chakraborty, Sankardeep and Sadakane, Kunihiko},
  title =	{{Indexing Graph Search Trees and Applications}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{67:1--67:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.67},
  URN =		{urn:nbn:de:0030-drops-110112},
  doi =		{10.4230/LIPIcs.MFCS.2019.67},
  annote =	{Keywords: Depth First Search Tree, Compact Data Structures, Encoding Schemes}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.13
A Framework for In-place Graph Algorithms

Authors: Sankardeep Chakraborty, Anish Mukherjee, Venkatesh Raman, and Srinivasa Rao Satti

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
Read-only memory (ROM) model is a classical model of computation to study time-space tradeoffs of algorithms. A classical result on the ROM model is that any algorithm to sort n numbers using O(s) words of extra space requires Omega (n^2/s) comparisons for lg n <= s <= n/lg n and the bound has also been recently matched by an algorithm. However, if we relax the model, we do have sorting algorithms (say Heapsort) that can sort using O(n lg n) comparisons using O(lg n) bits of extra space, even keeping a permutation of the given input sequence at anytime during the algorithm. We address similar relaxations for graph algorithms. We show that a simple natural relaxation of ROM model allows us to implement fundamental graph search methods like BFS and DFS more space efficiently than in ROM. By simply allowing elements in the adjacency list of a vertex to be permuted, we show that, on an undirected or directed connected graph G having n vertices and m edges, the vertices of G can be output in a DFS or BFS order using O(lg n) bits of extra space and O(n^3 lg n) time. Thus we obtain similar bounds for reachability and shortest path distance (both for undirected and directed graphs). With a little more (but still polynomial) time, we can also output vertices in the lex-DFS order. As reachability in directed graphs (even in DAGs) and shortest path distance (even in undirected graphs) are NL-complete, and lex-DFS is P-complete, our results show that our model is more powerful than ROM if L != P. En route, we also introduce and develop algorithms for another relaxation of ROM where the adjacency lists of the vertices are circular lists and we can modify only the heads of the lists. Here we first show a linear time DFS implementation using n + O(lg n) bits of extra space. Improving the extra space exponentially to only O(lg n) bits, we also obtain BFS and DFS albeit with a slightly slower running time. Both the models we propose maintain the graph structure throughout the algorithm, only the order of vertices in the adjacency list changes. In sharp contrast, for BFS and DFS, to the best of our knowledge, there are no algorithms in ROM that use even O(n^{1-epsilon}) bits of extra space; in fact, implementing DFS using cn bits for c<1 has been mentioned as an open problem. Furthermore, DFS (BFS, respectively) algorithms using n+o(n) (o(n), respectively) bits of extra use Reingold's [JACM, 2008] or Barnes et al's reachability algorithm [SICOMP, 1998] and hence have high runtime. Our results can be contrasted with the recent result of Buhrman et al. [STOC, 2014] which gives an algorithm for directed st-reachability on catalytic Turing machines using O(lg n) bits with catalytic space O(n^2 lg n) and time O(n^9).
Cite as

Sankardeep Chakraborty, Anish Mukherjee, Venkatesh Raman, and Srinivasa Rao Satti. A Framework for In-place Graph Algorithms. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ESA.2018.13,
  author =	{Chakraborty, Sankardeep and Mukherjee, Anish and Raman, Venkatesh and Satti, Srinivasa Rao},
  title =	{{A Framework for In-place Graph Algorithms}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.13},
  URN =		{urn:nbn:de:0030-drops-94760},
  doi =		{10.4230/LIPIcs.ESA.2018.13},
  annote =	{Keywords: DFS, BFS, in-place algorithm, space-efficient graph algorithms, logspace}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.22
Biconnectivity, Chain Decomposition and st-Numbering Using O(n) Bits

Authors: Sankardeep Chakraborty, Venkatesh Raman, and Srinivasa Rao Satti

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
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. Elmasry et al. gave, among others, an implementation of depth first search (DFS) of a graph on n vertices and m edges, taking O(m lg lg n) time using O(n) bits of space improving on the time bound of O(m lg n) due to Asano et al. Subsequently Banerjee et al. (COCOON 2016) gave an O(m + n) time implementation using O(m+n) bits, for DFS and its classical applications (including testing for biconnectivity, and finding cut vertices and cut edges). Recently, Kammer et al. (MFCS 2016) gave an algorithm for testing biconnectivity using O(n + min{m, n lg lg n}) bits in linear time. In this paper, we consider O(n) bits implementations of the classical applications of DFS. These include the problem of finding cut vertices, and biconnected components, chain decomposition and st-numbering. Classical algorithms for them typically use DFS and some Omega(lg n) bits of information at each node. Our O(n)-bit implementations for these problems take O(m lg^c n lg lg n) time for some small constant c (c leq 3). Central to our implementation is a succinct representation of the DFS tree and a space efficient partitioning of the DFS tree into connected subtrees, which maybe of independent interest for space efficient graph algorithms.
Cite as

Sankardeep Chakraborty, Venkatesh Raman, and Srinivasa Rao Satti. Biconnectivity, Chain Decomposition and st-Numbering Using O(n) Bits. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ISAAC.2016.22,
  author =	{Chakraborty, Sankardeep and Raman, Venkatesh and Satti, Srinivasa Rao},
  title =	{{Biconnectivity, Chain Decomposition and st-Numbering Using O(n) Bits}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.22},
  URN =		{urn:nbn:de:0030-drops-67927},
  doi =		{10.4230/LIPIcs.ISAAC.2016.22},
  annote =	{Keywords: biconnectivity, st-number, chain decomposition, tree cover, space efficient algorithms, read-only memory}
}
  • Refine by Author
  • 6 Chakraborty, Sankardeep
  • 4 Sadakane, Kunihiko
  • 4 Satti, Srinivasa Rao
  • 2 Raman, Venkatesh
  • 1 Balakrishnan, Girish
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Graph algorithms
  • 1 Information systems → Data structures
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Data structures design and analysis
  • 1 Theory of computation → Models of computation

  • Refine by Keyword
  • 1 BFS
  • 1 Blockchain
  • 1 Compact Data Structures
  • 1 DFS
  • 1 Depth First Search Tree
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 1 2016
  • 1 2018
  • 1 2019
  • 1 2020
  • 1 2022
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact