Succinct data structure for path graphs
Authors: 
Girish Balakrishnan, Sankardeep Chakraborty, N.S. Narayanaswamy, Kunihiko SadakaneAuthors Info & Claims
References
[1]
G. Balakrishnan, N.S. Narayanaswamy, S. Chakraborty, K. Sadakane, Succinct data structure for path graphs, in: Data Compression Conference, DCC 2022, IEEE, 2022, pp. 262–271.
[2]
D.D. Sleator, R.E. Tarjan, A data structure for dynamic trees, in: Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing, 1981, pp. 114–122.
[3]
V. Mäkinen, G. Navarro, Rank and select revisited and extended, Theor. Comput. Sci. 387 (3) (2007) 332–347.
[4]
M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, North-Holland Publishing Co., NLD, 2004.
[5]
H. Acan, S. Chakraborty, S. Jo, S.R. Satti, Succinct data structures for families of interval graphs, in: WADS, vol. 11646, 2019.
[6]
J.I. Munro, V. Raman, Succinct representation of balanced parentheses and static trees, SIAM J. Comput. 31 (3) (2001) 762–776.
[7]
L.C. Aleardi, O. Devillers, G. Schaeffer, Succinct representations of planar maps, Theor. Comput. Sci. 408 (2–3) (2008) 174–187.
[8]
A. Farzan, S. Kamali, Compact navigation and distance oracles for graphs with small treewidth, Algorithmica 69 (1) (2014) 92–116.
[9]
T. Yanagita, S. Chakraborty, K. Sadakane, S.R. Satti, Space-efficient data structure for posets with applications, in: 18th SWAT, in: LIPIcs, vol. 227, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, pp. 33:1–33:16.
[10]
S. Chakraborty, S. Jo, K. Sadakane, S.R. Satti, Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs, in: COCOA, in: Lecture Notes in Computer Science, vol. 13135, Springer, 2021, pp. 416–430.
[11]
H. Acan, S. Chakraborty, S. Jo, K. Nakashima, K. Sadakane, S.R. Satti, Succinct navigational oracles for families of intersection graphs on a circle, Theor. Comput. Sci. 928 (2022) 151–166.
[12]
S. Chakraborty, S. Jo, K. Sadakane, S.R. Satti, Succinct data structures for small clique-width graphs, in: DCC, IEEE, 2021, pp. 133–142.
[13]
J. Barbay, L.C. Aleardi, M. He, J.I. Munro, Succinct representation of labeled graphs, Algorithmica 62 (1–2) (2012) 224–257.
[14]
S. Kamali, Compact representation of graphs with bounded bandwidth or treedepth, Inf. Comput. 285 (Part) (2022).
[15]
S. Chakraborty, R. Grossi, K. Sadakane, S.R. Satti, Succinct representation for (non)deterministic finite automata, J. Comput. Syst. Sci. 131 (2023) 1–12.
[16]
A. Farzan, J.I. Munro, Succinct encoding of arbitrary graphs, Theor. Comput. Sci. 513 (2013) 38–52.
[17]
M. He, J.I. Munro, Y. Nekrich, S. Wild, K. Wu, Distance oracles for interval graphs via breadth-first rank/select in succinct trees, in: 31st ISAAC, in: LIPIcs, vol. 181, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, pp. 25:1–25:18.
[18]
S. Chakraborty, S. Jo, Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number, Theor. Comput. Sci. 941 (2023) 156–166.
[19]
J.I. Munro, K. Wu, Succinct data structures for chordal graphs, in: ISAAC, in: Leibniz International Proceedings in Informatics (LIPIcs), vol. 123, 2018, pp. 67:1–67:12.
[20]
P. Allen, V. Lozin, M. Rao, Clique-width and the speed of hereditary properties, Electron. J. Comb. 16 (1) (2009) R35.
[21]
D.G. Corneil, U. Rotics, On the relationship between clique-width and treewidth, in: Andreas Brandstädt, Van Bang Le (Eds.), Graph-Theoretic Concepts in Computer Science, Springer Berlin Heidelberg, Berlin, Heidelberg, 2001, pp. 78–90.
[22]
J. Böttcher, K.P. Pruessmann, A. Taraz, A. Würfl, Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs, Eur. J. Comb. 31 (5) (2010) 1217–1227.
[23]
F. Gavril, A Recognition Algorithm for the Intersection Graphs of Paths in Trees, 1978.
[24]
C.L. Monma, V.K.-W. Wei, Intersection graphs of paths in a tree, J. Comb. Theory, Ser. B 41 (2) (1986) 141–181.
[25]
R. Diestel, Graph Theory, 5th edition, Springer Publishing Company, Incorporated, 2017.
[26]
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd edition, The MIT Press, 2009.
[27]
P.L. Renz, Intersection representations of graphs by arcs, Pac. J. Math. 34 (2) (1970).
[28]
R. Grossi, G. Ottaviano, Fast compressed tries through path decompositions, ACM J. Exp. Algorithmics 19 (Jan. 2015).
[29]
P. Ferragina, R. Grossi, A. Gupta, R. Shah, J.S. Vitter, On searching compressed string collections cache-obliviously, in: PODS '08, ACM, 2008, pp. 181–190.
[30]
G. Navarro, K. Sadakane, Fully functional static and dynamic succinct trees, ACM Trans. Algorithms 10 (3) (May 2014).
[31]
R. Raman, V. Raman, S.R. Satti, Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets, ACM Trans. Algorithms 3 (4) (2007) 43.
[32]
G. Navarro, Compact Data Structures - a Practical Approach, Cambridge University Press, 2016.
[33]
A. Golynski, J.I. Munro, S.S. Rao, Rank/select operations on large alphabets: a tool for text indexing, in: SODA, USA, 2006, SODA '06, Society for Industrial and Applied Mathematics, 2006, pp. 368–373.
[34]
S. Chakraborty, K. Sadakane, Indexing graph search trees and applications, in: 44th MFCS, 2019, pp. 67:1–67:14.
[35]
N. Banerjee, S. Chakraborty, V. Raman, S.R. Satti, Space efficient linear time algorithms for BFS, DFS and applications, Theory Comput. Syst. 62 (8) (2018) 1736–1762.
[36]
S. Chakraborty, S.R. Satti, Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS, J. Comb. Optim. 37 (2) (2019) 465–481.
[37]
T. Hagerup, Fast breadth-first search in still less space, in: WG, in: Lecture Notes in Computer Science, vol. 11789, Springer, 2019, pp. 93–105.
[38]
T. Hagerup, Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster, Algorithmica 82 (4) (2020) 1033–1056.
Recommendations
I/O-Efficient Path Traversal in Succinct Planar Graphs
We present a technique for representing bounded-degree planar graphs in a succinct fashion while permitting I/O-efficient traversal of paths. Using our representation, a graph with N vertices, (In this paper $$\lg {N}$$lgN denotes $$\log _2{N}$$log2N) ...
Succinct encoding of arbitrary graphs
We consider the problem of encoding graphs with n vertices and m edges compactly supporting adjacency, neighborhood and degree queries in constant time in the @Q(logn)-bit word RAM model. The adjacency query asks whether there is an edge between two ...
Succinct representations of separable graphs
CPM'10: Proceedings of the 21st annual conference on Combinatorial pattern matchingWe consider the problem of highly space-efficient representation of separable graphs while supporting queries in constant time in the RAM with logarithmic word size. In particular, we show constant-time support for adjacency, degree and neighborhood ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Elsevier Inc.
Publisher
Academic Press, Inc.
United States
Publication History
Published: 12 April 2024
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 04 Jan 2025