Succinct posets

DOI10.1007/s00453-015-0047-1zbMath1347.68102OpenAlexW2911589947MaRDI QIDQ329288

Patrick K. Nicholson, J. Ian Munro

Publication date: 21 October 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-0047-1

zbMATH Keywords

data compressionZarankiewicz problempartial ordersrank and selectbalanced bipartite graphsgraph compressiongraph representationssuccinct data structure

Mathematics Subject Classification ID

Partial orders, general (06A06) Nonnumerical algorithms (68W05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)

Related Items (3)

Unnamed Item ⋮ Unnamed Item ⋮ Compact representation of graphs of small clique-width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Compact binary relation representations with rich functionality
• Succinct encoding of arbitrary graphs
• The complexity of embedding orders into small products of chains
• On locally presented posets
• Finding bipartite subgraphs efficiently
• Tree structure for distributive lattices and its applications
• Clique partitions, graph compression and speeding-up algorithms
• The average number of linear extensions of a partial order
• An efficient implicit data structure for relation testing and searching in partially ordered sets
• String realizers of posets with applications to distributed computing
• Sorting and Selection in Posets
• Compact Representation of Posets
• Succinct indexes for strings, binary relations and multilabeled trees
• The Hardness of Approximating Poset Dimension
• Approximate distance oracles
• The Complexity of the Partial Order Dimension Problem
• Asymptotic Enumeration of Partial Orders on a Finite Set
• An Efficient Data Structure for Lattice Operations
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Compact oracles for reachability and approximate distances in planar digraphs
• Probability and Computing
• Algorithms – ESA 2004
• The Number of Finite Topologies
• Lowest common ancestors in trees and directed acyclic graphs
• On a problem of K. Zarankiewicz
• Representing graphs implicitly using almost optimal space

This page was built for publication: Succinct posets