Minimizing setups in ordered sets of fixed width

Charles J. Colbourn; William R. Pulleyblank

doi:10.1007/BF00383598

Minimizing setups in ordered sets of fixed width

Charles J. Colbourn, William R. Pulleyblank

Research output: Contribution to journal › Article › peer-review

33 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	225-229
Number of pages	5
Journal	Order
Volume	1
Issue number	3
DOIs	https://doi.org/10.1007/BF00383598
State	Published - Sep 1985
Externally published	Yes

Keywords

AMS (MOS) subject classifications (1980): Primary 06A10, secondary 05C99, 68E99
dynamic programming
jump number
ordered set
polynomial time algorithm
setup number
width

ASJC Scopus subject areas

Algebra and Number Theory
Geometry and Topology
Computational Theory and Mathematics

Access to Document

10.1007/BF00383598

Cite this

@article{ea1ea0b7a6094125baa1b6f67b664b28,

title = "Minimizing setups in ordered sets of fixed width",

abstract = "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.",

keywords = "AMS (MOS) subject classifications (1980): Primary 06A10, secondary 05C99, 68E99, dynamic programming, jump number, ordered set, polynomial time algorithm, setup number, width",

author = "Colbourn, {Charles J.} and Pulleyblank, {William R.}",

year = "1985",

month = sep,

doi = "10.1007/BF00383598",

language = "English (US)",

volume = "1",

pages = "225--229",

journal = "Order",

issn = "0167-8094",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - Minimizing setups in ordered sets of fixed width

AU - Colbourn, Charles J.

AU - Pulleyblank, William R.

PY - 1985/9

Y1 - 1985/9

N2 - 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.

AB - 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.

KW - AMS (MOS) subject classifications (1980): Primary 06A10, secondary 05C99, 68E99

KW - dynamic programming

KW - jump number

KW - ordered set

KW - polynomial time algorithm

KW - setup number

KW - width

UR - http://www.scopus.com/inward/record.url?scp=0343695878&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0343695878&partnerID=8YFLogxK

U2 - 10.1007/BF00383598

DO - 10.1007/BF00383598

M3 - Article

AN - SCOPUS:0343695878

SN - 0167-8094

VL - 1

SP - 225

EP - 229

JO - Order

JF - Order

IS - 3

ER -

Minimizing setups in ordered sets of fixed width

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this