On finding the jump number of a partial order by substitution decomposition
type: Item
instance of: scholarly article
title: On finding the jump number of a partial order by substitution decomposition
zbMATH Open document ID: 0624.06002
DOI: 10.1007/BF00337920
author: George Steiner
published in: Order
publication date: 1985-01-01T00:00:00Z
review text: Consider the linear extensions of a partial order. A jump occurs in a linear extension if two consecutive elements are unrelated in the partial order. The jump number problem is to find a linear extension of the ordered set which contains the smallest possible number of jumps. We discuss a decomposition approach for this problem from an algorithmic point of view. Based on this some new classes of partial orders are identified, for which the problem is polynomially solvable.
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4012674
zbMATH Keywords: linear extensions
zbMATH Keywords: jump number problem
zbMATH Keywords: ordered set
zbMATH Keywords: partial orders
zbMATH Keywords: polynomially solvable
MaRDI profile type: Publication
cites work: A Fast Algorithm for the Decomposition of Graphs and Posets
cites work: The Jump Number of Dags and Posets: An Introduction
cites work: Q4200070
cites work: Decomposition of Directed Graphs
cites work: Minimizing Setups for Cycle-Free Ordered Sets
cites work: Q3329227
cites work: Transitiv orientierbare Graphen
cites work: Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
cites work: Comparability graphs and a new matroid
cites work: On the X-join decomposition for undirected graphs
cites work: Q3691784
cites work: Q3686754
cites work: Optimal Linear Extensions by Interchanging Chains
cites work: A labeling algorithm to recognize a line digraph and output its root graph
cites work: Minimizing the jump number for partially ordered sets: A graph-theoretic approach
cites work: The Recognition of Series Parallel Digraphs
description: scientific article; zbMATH DE number 4012674