On minimizing the jump number for interval orders

DOI10.1007/BF00714476MaRDI QIDQ1111581zbMATH OpenOpenAlexFDO

Authors Tashin Ghazal, Nejib Zaguia, Ahmad H. Sharary

Publication date 1988

Published in Order (Search for Journal in Brave)

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

zbMATH Keywords

interval ordersjump numbergreedy linear extensionsgreedy poset probleminterval posets

Mathematics Subject Classification ID

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

Recommendations

• Minimizing the jump number for partially-ordered sets: A graph-theoretic approach. II
• Greedy linear extensions to minimize jumps
• Greedy posets for the bump-minimizing problem
• A 3/2-approximation algorithm for the jump number of interval orders
• On some new types of greedy chains and greedy linear extensions of partially ordered sets

Cites work

• Constructing greedy linear extensions by interchanging chains
• Greedy linear extensions with constraints
• NP-completeness results concerning greedy and super greedy linear extensions
• Optimal Linear Extensions by Interchanging Chains

Cited in

(10)

• A polynomially solvable case of optimal linear extension problem of a poset
• A 3/2-approximation algorithm for the jump number of interval orders
• scientific article; zbMATH DE number 822739 (Why is no real title available?)
• On some new types of greedy chains and greedy linear extensions of partially ordered sets
• scientific article; zbMATH DE number 786159 (Why is no real title available?)
• Scheduling tasks on a flexible manufacturing machine to minimize tool change delays
• Greedy posets for the bump-minimizing problem
• scientific article; zbMATH DE number 3948306 (Why is no real title available?)
• Minimizing the maximum bump cost in linear extensions of a poset
• Jumps of Orderings

This page was built for publication: On minimizing the jump number for interval orders

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