Minimizing bumps for posets of width two
type: Item
instance of: scholarly article
title: Minimizing bumps for posets of width two
zbMATH Open document ID: 0663.06002
DOI: 10.1016/0166-218X(88)90051-0
author: Nejib Zaguia
published in: Discrete Applied Mathematics
publication date: 1988-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 06A06
zbMATH DE Number: 4083687
zbMATH Keywords: linear extension of a finite partially ordered set
zbMATH Keywords: linear extension with a minimum number of bumps
reviewed by: Richard A. Aló
MaRDI profile type: Publication
cites work: Jump number of dags having Dilworth number 2
cites work: Minimizing setups in ordered sets of fixed width
cites work: Minimizing Setups for Cycle-Free Ordered Sets
cites work: Minimizing bumps in linear extensions of ordered sets
cites work: Optimal Linear Extensions by Interchanging Chains
cites work: Constructing greedy linear extensions by interchanging chains
cites work: Q3927277
description: scientific article; zbMATH DE number 4083687