Succinct posets

DOI10.1007/S00453-015-0047-1zbMATH Open1347.68102OpenAlexW2911589947MaRDI QIDQ329288FDOQ329288

Authors: J. Ian Munro, Patrick K. Nicholson 

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

Recommendations

• Succinct posets
• Compact representation of posets
• Succinct data structures for families of interval graphs
• Succinct representations of ordinal trees
• scientific article; zbMATH DE number 4047144

zbMATH Keywords

partial ordersdata compressionZarankiewicz problemrank and selectbalanced bipartite graphsgraph compressiongraph representationssuccinct data structure

Mathematics Subject Classification ID

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

Cites Work

• Introduction to algorithms.
• Asymptotic Enumeration of Partial Orders on a Finite Set
• Approximate distance oracles
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Algorithms – ESA 2004
• Lowest common ancestors in trees and directed acyclic graphs
• Succinct indexes for strings, binary relations and multilabeled trees
• On a problem of K. Zarankiewicz
• The Complexity of the Partial Order Dimension Problem
• Title not available (Why is that?)
• Probability and Computing
• Succinct indexes for strings, binary relations and multi-labeled trees
• Title not available (Why is that?)
• Compact oracles for reachability and approximate distances in planar digraphs
• Representing graphs implicitly using almost optimal space
• 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
• The Hardness of Approximating Poset Dimension
• Title not available (Why is that?)
• Title not available (Why is that?)
• Compact binary relation representations with rich functionality
• Succinct encoding of arbitrary graphs
• An Efficient Data Structure for Lattice Operations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Number of Finite Topologies
• The complexity of embedding orders into small products of chains
• On locally presented posets
• Finding bipartite subgraphs efficiently

Cited In (6)

• Title not available (Why is that?)
• Compact representation of graphs of small clique-width
• Succinct posets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Compact representation of posets

This page was built for publication: Succinct posets

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