Minimizing setups in ordered sets of fixed width
type: Item
instance of: scholarly article
title: Minimizing setups in ordered sets of fixed width
zbMATH Open document ID: 0557.06002
DOI: 10.1007/BF00383598
author: William R. Pulleyblank
author: Charles J. Colbourn
published in: Order
publication date: 1985-01-01T00:00:00Z
review text: If P is a poset then the width is the minimum number of chains which cover all elements of the ordered set. If L is a linear extension of P, then s(P,L) is the number of pairs \((x_ i,x_{i+1})\) which are not related in P, but are consecutive in L. The setup number s(P) is the minimum of the numbers s(P,L). In this concise paper the authors provide an elegant polynomial time algorithm for computing the setup number of an ordered set with fixed width (Dilworth number). This generalizes work by Chein and Habib and falls in a class of different algorithms for different classes of posets, several discussed by the same authors elsewhere.
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 05A15
zbMATH DE Number: 3887750
zbMATH Keywords: width
zbMATH Keywords: chains
zbMATH Keywords: linear extension
zbMATH Keywords: setup number
zbMATH Keywords: polynomial time algorithm
zbMATH Keywords: Dilworth number
zbMATH Keywords: posets
reviewed by: J. Neggers
MaRDI profile type: Publication
cites work: Jump number of dags having Dilworth number 2
cites work: Minimizing Setups for Cycle-Free Ordered Sets
cites work: Minimizing completion time for a class of scheduling problems
cites work: Complexity of Scheduling under Precedence Constraints
cites work: Q3698661
cites work: Minimizing the jump number for partially ordered sets: A graph-theoretic approach
cites work: Q3676161
Recommended article: On linear sets of minimum size
Recommended article: Minimum d-dimensional arrangement with fixed points
Recommended article: Minimal separating sets of maximum size
Recommended article: On minimizing jumps for ordered sets
Recommended article: Minimizing bumps for posets of width two
Recommended article: Q4017185
Recommended article: Minimum linear arrangements
Recommended article: Decorous lower bounds for minimum linear arrangement
Recommended article: Q4796669
Recommended article: Q4518696
description: scientific article; zbMATH DE number 3887750