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