On minimizing jumps for ordered sets

DOI10.1007/BF00383200MaRDI QIDQ1177708zbMATH OpenFDO

Authors Ahmad H. Sharary, Nejib Zaguia

Publication date 26 June 1992

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00383200

zbMATH Keywords

jump numberlinear extensionspartially ordered setpolynomial time algorithm

Mathematics Subject Classification ID

Partial orders, general (06A06) Combinatorics of partially ordered sets (06A07) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Review text

Extending a partially ordered set to a chain decomposes the poset into a number of chains. The minimal possible number is the jump number of the poset. The paper presents a polynomial time algorithm to find this number for any poset \(P\) not containing a \(4\)-element subset \(\{a,b,c,d\}\) with \(a<b\) being the only comparability in \(P\) between those elements.

Recommendations

• An optimal algorithm to find the jump number of partially ordered sets
• Minimizing the jump number for partially-ordered sets: A graph-theoretic approach. II
• scientific article; zbMATH DE number 19350
• The jump number of Z-free ordered sets

Cites work

• A 3/2-approximation algorithm for the jump number of interval orders
• A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders
• Constructing greedy linear extensions by interchanging chains
• scientific article; zbMATH DE number 3641455 (Why is no real title available?)
• Jump number of dags having Dilworth number 2
• Minimizing Setups for Cycle-Free Ordered Sets
• Minimizing setups in ordered sets of fixed width
• NP-completeness properties about linear extensions
• On a setup optimization problem for interval orders
• Optimal Linear Extensions by Interchanging Chains

Cited in

(15)

• Minimizing the jump number for partially ordered sets: A graph-theoretic approach
• On finding the jump number of a partial order by substitution decomposition
• The jump number of Z-free ordered sets
• Maximum and minimum jump number of posets from matrices
• On the poset of all posets on n elements
• An optimal algorithm to find the jump number of partially ordered sets
• The arboreal jump number of an order
• scientific article; zbMATH DE number 4019120 (Why is no real title available?)
• Jumps of Orderings
• Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings
• scientific article; zbMATH DE number 19350 (Why is no real title available?)
• Jumps of Hemimaximal Sets
• Minimizing the sum cost in linear extensions of a poset
• Minimizing setups in ordered sets of fixed width
• On the size of jump-critical ordered sets

This page was built for publication: On minimizing jumps for ordered sets

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