Heapability, interactive particle systems, partial orders: results and open problems

DOI10.1007/978-3-319-41114-9_2MaRDI QIDQ2829966zbMATH OpenOpenAlexFDO

Authors Cosmin Bonchiş, Gabriel 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

heapable sequencesposets

Mathematics Subject Classification ID

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

Recommendations

• On the heapability of finite partial orders
• Partition into heapable sequences, heap tableaux and a multiset extension of Hammersley's process
• Heapable sequences and subsequences
• Sortabilities of partition properties
• Heap-orderd trees, 2-partitions and continued fractions

Cites work

• A decomposition theorem for partially ordered sets
• A variational problem for random Young tableaux
• An upper bound on the number of high-dimensional permutations
• Covering and coloring problems for relatives of intervals
• Functional Compression Through Graph Coloring
• Hammersley's interacting particle process and longest increasing subsequences
• scientific article; zbMATH DE number 446489 (Why is no real title available?)
• scientific article; zbMATH DE number 3630761 (Why is no real title available?)
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• scientific article; zbMATH DE number 3373691 (Why is no real title available?)
• Hydrodynamical methods for analyzing longest increasing subsequences
• Minimum entropy combinatorial optimization problems
• Minimum entropy orientations
• Monotone subsequences in high-dimensional permutations
• On compressing permutations and adaptive sorting
• On the entropy of couplings
• Partition into heapable sequences, heap tableaux and a multiset extension of Hammersley's process
• Random k-dimensional orders: Width and number of linear extensions
• Random orders
• Source coding and graph entropies
• The height of a random partial order: Concentration of measure
• The Longest Chain Among Random Points in Euclidean Space
• The minimum entropy submodular set cover problem
• The minimum-entropy set cover problem
• The surprising mathematics of longest increasing subsequences
• Tight results on minimum entropy set cover

Cited in

(7)

• The maximum binary tree problem
• Mixing times for exclusion processes on hypergraphs
• Partition into heapable sequences, heap tableaux and a multiset extension of Hammersley's process
• On the heapability of finite partial orders
• Heapable sequences and subsequences
• The Maximum Binary Tree Problem.
• Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree

This page was built for publication: Heapability, interactive particle systems, partial orders: results and open problems

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