On finding the jump number of a partial order by substitution decomposition

DOI10.1007/BF00337920zbMath0624.06002MaRDI QIDQ1092072

George Steiner

Publication date: 1985

Published in: Order (Search for Journal in Brave)

zbMATH Keywords

ordered setpartial orderslinear extensionsjump number problempolynomially solvable

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06)

Related Items (8)

Minimizing bumps in linear extensions of ordered sets ⋮ Greedy posets for the bump-minimizing problem ⋮ Substitution and atomic extension on greedy posets ⋮ `Strong'-`weak' precedence in scheduling: extensions to series-parallel orders ⋮ The arboreal jump number of an order ⋮ A 3/2-approximation algorithm for the jump number of interval orders ⋮ \(P_ 4\)-trees and substitution decomposition ⋮ Single machine scheduling with precedence constraints and positionally dependent processing times

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimizing the jump number for partially ordered sets: A graph-theoretic approach
• On the X-join decomposition for undirected graphs
• A labeling algorithm to recognize a line digraph and output its root graph
• Comparability graphs and a new matroid
• A Fast Algorithm for the Decomposition of Graphs and Posets
• Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
• Optimal Linear Extensions by Interchanging Chains
• The Jump Number of Dags and Posets: An Introduction
• The Recognition of Series Parallel Digraphs
• Decomposition of Directed Graphs
• Minimizing Setups for Cycle-Free Ordered Sets
• Transitiv orientierbare Graphen

This page was built for publication: On finding the jump number of a partial order by substitution decomposition