Computing the number of mergings with constraints

DOI10.1016/0020-0190(87)90151-7MaRDI QIDQ1108016zbMATH OpenOpenAlexFDO

Authors S. H. Smith

Publication date 1987

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(87)90151-7

zbMATH Keywords

Catalan numbersFibonacci numberslinear extensionmerging

Mathematics Subject Classification ID

Partial orders, general (06A06) Fibonacci and Lucas numbers and polynomials and generalizations (11B39) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 3990870
• Optimal expected-time algorithms for merging
• Bounds on the size of merging networks
• Simplified stable merging tasks
• Average-case analysis of the merging algorithm of Hwang and Lin

Cites work

• scientific article; zbMATH DE number 4027523 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• The Information-Theoretic Bound is Good for Merging

Cited in

(15)

• Counting linear extensions
• Balanced pairs in partial orders
• Bounded capacity priority queues
• Reaching the bound in the \((2,n)\) merging problem
• Merging ordered sets.
• scientific article; zbMATH DE number 3990870 (Why is no real title available?)
• Proper mergings of stars and chains are counted by sums of antidiagonals in certain convolution arrays
• Merging-free partitions and run-sorted permutations
• Projection merging
• The worst balanced partially ordered sets-ladders with broken rungs
• Poset entropy versus number of linear extensions: the width-2 case.
• A combinatorial model for lane merging
• Combinatorial and geometric approaches to counting problems on linear matroids, graphic arrangements, and partial orders
• The Ford-Johnson algorithm still unbeaten for less than 47 elements
• Disjunctive merging: quota and Gmin merging operators

This page was built for publication: Computing the number of mergings with constraints

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