✦ LIBER ✦

Minimizing setups in ordered sets of fixed width

✍ Scribed by Charles J. Colbourn; William R. Pulleyblank

Publisher: Springer Netherlands
Year: 1985
Tongue: English
Weight: 190 KB
Volume: 1
Category: Article
ISSN: 0167-8094
DOI: 10.1007/bf00383598

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

The fixed point property in ordered sets

The fixed point property in ordered sets of width two

✍ Tatyana S. Fofanova; Aleksander Rutkowski 📂 Article 📅 1987 🏛 Springer Netherlands 🌐 English ⚖ 303 KB

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

Fibres of width 3 ordered sets

✍ Zbigniew Lonc 📂 Article 📅 1994 🏛 Springer Netherlands 🌐 English ⚖ 617 KB

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

On the width of ordered sets and Boolean

On the width of ordered sets and Boolean algebras

✍ E. C. Milner; M. Pouzet 📂 Article 📅 1986 🏛 Springer 🌐 English ⚖ 683 KB

Fixed point theorems for weakly contract

Fixed point theorems for weakly contractive mappings in partially ordered sets

✍ J. Harjani; K. Sadarangani 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 479 KB

The purpose of this paper is to present some fixed point theorems for weakly contractive maps in a complete metric space endowed with a partial order.