Succinct encoding of arbitrary graphs

DOI10.1016/J.TCS.2013.09.031MaRDI QIDQ391972zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Succinct Representations of Arbitrary Graphs
• Succinct Encodings of Graph Isomorphism
• On the succinct representation of graphs
• Succinct representations of graphs
• A note on succinct representations of graphs
• Bounded-depth succinct encodings and the structure they imply on graphs
• Succinct encodings for families of interval graphs
• Succinct representations of separable graphs
• scientific article; zbMATH DE number 2032369

Cites work

• scientific article; zbMATH DE number 1688373 (Why is no real title available?)
• scientific article; zbMATH DE number 5506222 (Why is no real title available?)
• scientific article; zbMATH DE number 2038722 (Why is no real title available?)
• scientific article; zbMATH DE number 2079399 (Why is no real title available?)
• Adaptive Searching in Succinctly Encoded Binary Relations and Tree-Structured Documents
• An introduction to Kolmogorov complexity and its applications
• Automata, Languages and Programming
• Implicat Representation of Graphs
• Low redundancy in static dictionaries with constant query time
• Membership in Constant Time and Almost-Minimum Space
• New lower and upper bounds for representing sequences
• On the succinct representation of graphs
• Optimal bounds for the predecessor problem and related problems
• Optimal trade-offs for succinct string indexes
• Rank/select operations on large alphabets
• Short encodings of planar graphs and maps
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Succinct Representations of Arbitrary Graphs
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
• Succinct indexes for strings, binary relations and multi-labeled trees

Cited in

(22)

• Extra space during initialization of succinct data structures and dynamical initializable arrays
• Succinct encoding of binary strings representing triangulations
• Succinct Representations of Arbitrary Graphs
• Succinct data structures for SP, block-cactus and \(3\)-leaf power graphs
• Succinct encodings for families of interval graphs
• Succinct representations for (non)deterministic finite automata
• Succinct representation for (non)deterministic finite automata
• Succinct data structures for bounded clique-width graphs
• Succinct Encodings of Graph Isomorphism
• Succinct navigational oracles for families of intersection graphs on a circle
• scientific article; zbMATH DE number 4139806 (Why is no real title available?)
• Succinct data structure for path graphs
• Compact representation of graphs with bounded bandwidth or treedepth
• Succinct data structures for families of interval graphs
• A note on succinct representations of graphs
• Frameworks for designing in-place graph algorithms
• Adjacency labeling schemes and induced-universal graphs
• Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs
• Succinct posets
• scientific article; zbMATH DE number 7561421 (Why is no real title available?)
• Encoding data structures
• On the succinct representation of graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q391972)