Minimizing Setups for Cycle-Free Ordered Sets

DOI10.2307/2044053MaRDI QIDQ3960747zbMATH OpenOpenAlexFDO

Authors Dwight Duffus, Ivan Rival, Peter Winkler

Publication date 1982

Full work available at URL https://doi.org/10.2307/2044053

zbMATH Keywords

alternating cycleslinear extensions of ordered setsminimizing setups

Mathematics Subject Classification ID

Partial orders, general (06A06) Programming involving graphs or networks (90C35)

Cites work

• A decomposition theorem for partially ordered sets
• scientific article; zbMATH DE number 3485834 (Why is no real title available?)
• scientific article; zbMATH DE number 3641455 (Why is no real title available?)
• scientific article; zbMATH DE number 3375519 (Why is no real title available?)
• The Jump Number of Dags and Posets: An Introduction

Cited in

(33)

• Jump number problem: The role of matroids
• An algorithm for minimizing setups in precedence constrained scheduling
• Chordal bipartite graphs and crowns
• Interval orders without odd crowns are defect optimal
• A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders
• On finding the jump number of a partial order by substitution decomposition
• Greedy posets for the bump-minimizing problem
• Minimizing bumps for posets of width two
• On minimizing jumps for ordered sets
• Cycle-free partial orders and chordal comparability graphs
• A greedy reduction algorithm for setup optimization
• The jump number of Z-free ordered sets
• Maximum and minimum jump number of posets from matrices
• On a setup optimization problem for interval orders
• Some new explorations into the mystery of time and band limiting
• Semantic networks
• Alternating cycle-free matchings
• On the poset of all posets on n elements
• Split orders
• An improved algorithm for the jump number problem
• Obituary: Ivan Rival
• The arboreal jump number of an order
• Scheduling with few changes
• Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings
• Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
• Optimal Linear Extensions by Interchanging Chains
• Minimizing the maximum bump cost in linear extensions of a poset
• NP-completeness properties about linear extensions
• A polynomially solvable case of optimal linear extension problem of a poset
• Minimizing the sum cost in linear extensions of a poset
• Minimizing setups in ordered sets of fixed width
• Jump number of dags having Dilworth number 2
• A 3/2-approximation algorithm for the jump number of interval orders

This page was built for publication: Minimizing Setups for Cycle-Free Ordered Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3960747)