𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Minimizing bumps in linear extensions of ordered sets

✍ Scribed by Peter C. Fishburn; William V. Gehrlein

Publisher
Springer Netherlands
Year
1986
Tongue
English
Weight
650 KB
Volume
3
Category
Article
ISSN
0167-8094

No coin nor oath required. For personal study only.

✦ Synopsis

A linear extension x,x2xs ... of a partially ordered set (X, <) has a bump whenever xi < xi+l. We examine the problem of determining linear extensions with as few bumps as possible. Heuristic algorithms for approximate bump minimization are considered. AhfS (MOS) subject classifications (1980). Primary 06A10, secondary 68C25.

πŸ“œ SIMILAR VOLUMES

Minimizing bumps in ordered sets by subs
Minimizing bumps in ordered sets by substitution decomposition
✍ George Steiner πŸ“‚ Article πŸ“… 1989 πŸ› Elsevier Science 🌐 English βš– 495 KB

A linear extension x1x2. . . x, of a partially or&red set P has a bump whenever Xi <xi+1 in P. The bump number problem is to find a linear extension of P with the smallest possible number of bumps. We present a basic decomposition theorem for this problem. This leads to simple formulae for the bump