Heapability, Interactive Particle Systems, Partial Orders: Results and Open Problems

DOI10.1007/978-3-319-41114-9_2zbMath1476.68187OpenAlexW2490801230MaRDI QIDQ2829966

Cosmin Bonchiş, Gabriel I. Istrate

Publication date: 9 November 2016

Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01633954/file/416473_1_En_2_Chapter.pdf

zbMATH Keywords

posetsheapable sequences

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Combinatorics of partially ordered sets (06A07) Data structures (68P05)

Related Items (4)

The Maximum Binary Tree Problem. ⋮ Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree ⋮ The maximum binary tree problem ⋮ Mixing times for exclusion processes on hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On compressing permutations and adaptive sorting
• An upper bound on the number of high-dimensional permutations
• Random \(k\)-dimensional orders: Width and number of linear extensions
• Tight results on minimum entropy set cover
• Random orders
• Covering and coloring problems for relatives of intervals
• The height of a random partial order: Concentration of measure
• A variational problem for random Young tableaux
• Hydrodynamical methods for analyzing longest increasing subsequences
• Hammersley's interacting particle process and longest increasing subsequences
• On the entropy of couplings
• Minimum entropy orientations
• The minimum-entropy set cover problem
• A decomposition theorem for partially ordered sets
• The Minimum Entropy Submodular Set Cover Problem
• The Surprising Mathematics of Longest Increasing Subsequences
• Partition into Heapable Sequences, Heap Tableaux and a Multiset Extension of Hammersley’s Process
• Minimum Entropy Combinatorial Optimization Problems
• The Longest Chain Among Random Points in Euclidean Space
• Monotone Subsequences in High-Dimensional Permutations
• Source coding and graph entropies
• Functional Compression Through Graph Coloring

This page was built for publication: Heapability, Interactive Particle Systems, Partial Orders: Results and Open Problems