Succinct encoding of arbitrary graphs

DOI10.1016/j.tcs.2013.09.031zbMath1407.68356OpenAlexW1993294649MaRDI QIDQ391972

Arash Farzan, J. Ian Munro

Publication date: 13 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.09.031

zbMATH Keywords

compressiongraph encodingsuccinct representation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Related Items (13)

Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs ⋮ Succinct posets ⋮ Adjacency Labeling Schemes and Induced-Universal Graphs ⋮ Succinct encodings for families of interval graphs ⋮ Succinct encoding of binary strings representing triangulations ⋮ Compact representation of graphs with bounded bandwidth or treedepth ⋮ Succinct data structure for path graphs ⋮ Succinct representations for (non)deterministic finite automata ⋮ Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays. ⋮ Frameworks for designing in-place graph algorithms ⋮ Unnamed Item ⋮ Succinct navigational oracles for families of intersection graphs on a circle ⋮ Succinct representation for (non)deterministic finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the succinct representation of graphs
• Short encodings of planar graphs and maps
• Optimal bounds for the predecessor problem and related problems
• Low Redundancy in Static Dictionaries with Constant Query Time
• New Lower and Upper Bounds for Representing Sequences
• Succinct Representations of Arbitrary Graphs
• Rank/select operations on large alphabets
• Optimal Trade-Offs for Succinct String Indexes
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Implicat Representation of Graphs
• Membership in Constant Time and Almost-Minimum Space
• Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
• Adaptive Searching in Succinctly Encoded Binary Relations and Tree-Structured Documents
• Automata, Languages and Programming
• An introduction to Kolmogorov complexity and its applications

This page was built for publication: Succinct encoding of arbitrary graphs