On minimizing the jump number for interval orders

DOI10.1007/BF00714476zbMath0658.06001OpenAlexW2054170773MaRDI QIDQ1111581

Nejib Zaguia, Tashin Ghazal, 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

jump numberinterval ordersgreedy linear extensionsgreedy poset probleminterval posets

Mathematics Subject Classification ID

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

Related Items

Minimizing the maximum bump cost in linear extensions of a poset ⋮ A polynomially solvable case of optimal linear extension problem of a poset ⋮ A 3/2-approximation algorithm for the jump number of interval orders ⋮ Scheduling tasks on a flexible manufacturing machine to minimize tool change delays

Cites Work

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