๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Minimizing bumps in ordered sets by substitution decomposition

โœ Scribed by George Steiner

Publisher
Elsevier Science
Year
1989
Tongue
English
Weight
495 KB
Volume
76
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 number of series-parallel posets.

๐Ÿ“œ SIMILAR VOLUMES

Minimizing bumps in linear extensions of
Minimizing bumps in linear extensions of ordered sets
โœ Peter C. Fishburn; William V. Gehrlein ๐Ÿ“‚ Article ๐Ÿ“… 1986 ๐Ÿ› Springer Netherlands ๐ŸŒ English โš– 650 KB

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). Prim

Minimizing setups in ordered sets of fix
Minimizing setups in ordered sets of fixed width
โœ Charles J. Colbourn; William R. Pulleyblank ๐Ÿ“‚ Article ๐Ÿ“… 1985 ๐Ÿ› Springer Netherlands ๐ŸŒ English โš– 190 KB

A simply polynomial time algorithm is given for computing the setup number, or jump number, of an ordered set with fixed width. This arises as an interesting application of a polynomial time algorithm for solving a more general weighted problem in precedence constrained scheduling.