On minimizing jumps for ordered sets

DOI10.1007/BF00383200zbMath0735.06002MaRDI QIDQ1177708

Nejib Zaguia, Ahmad H. Sharary

Publication date: 26 June 1992

Published in: Order (Search for Journal in Brave)

zbMATH Keywords

polynomial time algorithmpartially ordered setjump numberlinear extensions

Mathematics Subject Classification ID

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

Related Items (3)

Minimizing the sum cost in linear extensions of a poset ⋮ The jump number of Z-free ordered sets ⋮ Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings

Cites Work

• Unnamed Item
• NP-completeness properties about linear extensions
• Minimizing setups in ordered sets of fixed width
• Jump number of dags having Dilworth number 2
• A 3/2-approximation algorithm for the jump number of interval orders
• Constructing greedy linear extensions by interchanging chains
• A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders
• On a setup optimization problem for interval orders
• Optimal Linear Extensions by Interchanging Chains
• Minimizing Setups for Cycle-Free Ordered Sets

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