Succinct Representation of Balanced Parentheses and Static Trees
From MaRDI portal
Publication:2784479
DOI10.1137/S0097539799364092zbMath1017.68037MaRDI QIDQ2784479
Publication date: 23 April 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
planar graphs; binary trees; succinct representation; abstract data type; rooted ordered trees; balanced parenthesis
Related Items
Unnamed Item, Unnamed Item, Recent Developments in Floorplan Representations, PARENT QUERIES OVER DYNAMIC BALANCED PARENTHESIS STRINGS, Random Access to Grammar-Compressed Strings and Trees, Practical Compact Indexes for Top-kDocument Retrieval, Space-Efficient Euler Partition and Bipartite Edge Coloring, Succinct Representation of Labeled Graphs, A Compact Encoding of Plane Triangulations with Efficient Query Supports, Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space, Efficient and compact representations of some non-canonical prefix-free codes, Compressed indexes for approximate string matching, Fast and compact planar embeddings, Efficient computation of Lyapunov functions for Morse decompositions, Succinct dynamic cardinal trees, Compressed string dictionary search with edit distance one, Simultaneous encodings for range and next/previous larger/smaller value queries, Compressed indexes for text with wildcards, On-line construction of position heaps, A compact encoding of plane triangulations with efficient query supports, Random generation and enumeration of bipartite permutation graphs, Ultra-succinct representation of ordered trees with applications, Succinct representations of permutations and functions, On the approximability of some degree-constrained subgraph problems, Compact navigation and distance oracles for graphs with small treewidth, Succinct representation of labeled trees, Simple and efficient fully-functional succinct trees, Combined data structure for previous- and next-smaller-values, Space-efficient construction of Lempel-Ziv compressed text indexes, Succinct data structures for searchable partial sums with optimal worst-case performance, On the complexity of isoperimetric problems on trees, Graph compression and the zeros of polynomials, A simple optimal representation for balanced parentheses, Succinct data structures for flexible text retrieval systems, Improved approximate string matching using compressed suffix data structures, Succinct representations of planar maps, On compact representations of all-pairs-shortest-path-distance matrices, Compressing probability distributions, Space-efficient Euler partition and bipartite edge coloring, Path queries on functions, Tree compression using string grammars, Dynamic path queries in linear space, Flexible indexing of repetitive collections, The space complexity of sum labelling, Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs, Block trees, Succinct representations for (non)deterministic finite automata, Lempel-Ziv compressed structures for document retrieval, Linear-time algorithms for tree root problems, Tree compression with top trees, Linked dynamic tries with applications to LZ-compression in sublinear time and space, Succinct indices for path minimum, with applications, On succinct representations of binary trees, Succinct representations of weighted trees supporting path queries, Constructing small tree grammars and small circuits for formulas, Improved range minimum queries, Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits, Succinct data structure for dynamic trees with faster queries, Stronger Lempel-Ziv based compressed text indexing, Succinct representation of labeled graphs, Succinct and I/O efficient data structures for traversal in trees, Adaptive searching in succinctly encoded binary relations and tree-structured documents, Truly selective polygonal mesh hierarchies with error control, GLOUDS: representing tree-like graphs, Representation of ordered trees with a given degree distribution, Succinct encodings for families of interval graphs, Encoding two-dimensional range top-\(k\) queries, Succinct encoding of binary strings representing triangulations, Fully Functional Static and Dynamic Succinct Trees, Fast Compressed Tries through Path Decompositions, General Document Retrieval in Compact Space, BOUNDING THE NUMBER OF REDUCED TREES, COGRAPHS, AND SERIES-PARALLEL GRAPHS BY COMPRESSION, Succinct and Implicit Data Structures for Computational Geometry, Succinct Representations of Ordinal Trees, Encodings of Range Maximum-Sum Segment Queries and Applications, A Compact Encoding of Unordered Binary Trees, Succincter Text Indexing with Wildcards, Unnamed Item, Degree-Constrained Subgraph Problems: Hardness and Approximation Results, Random Generation and Enumeration of Proper Interval Graphs
