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

On minimizing jumps for ordered sets

โœ Scribed by Ahmad H. Sharary; Nejib Zaguia

Publisher
Springer Netherlands
Year
1991
Tongue
English
Weight
383 KB
Volume
7
Category
Article
ISSN
0167-8094

No coin nor oath required. For personal study only.

โœฆ Synopsis

An ordered set P is called K-free if it does not contain a four-element subset {a, b, c, d} such that a <b is the only comparability among these elements. In this paper we present a polynomial algorithm to find the jump number of K-free ordered sets.

AMS subject classifications (1980). 06Al& &X15.

๐Ÿ“œ 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

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.

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

On the size of jump-critical ordered set
On the size of jump-critical ordered sets
โœ M. H. El-Zahar; J. H. Schmerl ๐Ÿ“‚ Article ๐Ÿ“… 1984 ๐Ÿ› Springer Netherlands ๐ŸŒ English โš– 150 KB

The maximum size of a jump-critical ordered set with jump-number m is at most (m + l)! AMS (MOS) subject classifications (1980). Primary 06AlO; secondary 68C25.