Minimizing bumps for posets of width two

DOI10.1016/0166-218X(88)90051-0MaRDI QIDQ1114719zbMATH OpenFDO

Authors Nejib Zaguia

Publication date 1988

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(88)90051-0

zbMATH Keywords

linear extension of a finite partially ordered setlinear extension with a minimum number of bumps

Mathematics Subject Classification ID

Partial orders, general (06A06)

Review text

Let \(L=\{x_ 1<...<x_ n\}\) be a linear extension of a finite partially ordered set P. A pair \((x_ i,x_ i+1)\) forms a bump in L whenever \(x_ i<x_ i+1\) in P. The author gives an effective solution for the problem of finding a linear extension with a minimum number of bumps when the width of P is two.

Recommendations

• Minimizing bumps in linear extensions of ordered sets
• Minimizing bumps in ordered sets by substitution decomposition
• Greedy linear extensions for minimizing bumps
• A comparison of algorithms for minimizing bumps in linear extensions of partial orders
• Greedy posets for the bump-minimizing problem

Cites work

• Constructing greedy linear extensions by interchanging chains
• scientific article; zbMATH DE number 3741435 (Why is no real title available?)
• Jump number of dags having Dilworth number 2
• Minimizing bumps in linear extensions of ordered sets
• Minimizing Setups for Cycle-Free Ordered Sets
• Minimizing setups in ordered sets of fixed width
• Optimal Linear Extensions by Interchanging Chains

Cited in

(10)

• Minimizing bumps in linear extensions of ordered sets
• Greedy linear extensions for minimizing bumps
• Greedy posets for the bump-minimizing problem
• Computing the bump number is easy
• Computing the bump number with techniques from two-processor scheduling
• Minimizing bumps in ordered sets by substitution decomposition
• A comparison of algorithms for minimizing bumps in linear extensions of partial orders
• Generating linear extensions of posets by transpositions
• Minimizing the maximum bump cost in linear extensions of a poset
• Minimizing setups in ordered sets of fixed width

This page was built for publication: Minimizing bumps for posets of width two

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