On minimizing the jump number for interval orders

DOI10.1007/BF00714476zbMATH Open0658.06001OpenAlexW2054170773MaRDI QIDQ1111581FDOQ1111581

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• On some new types of greedy chains and greedy linear extensions of partially ordered sets
• Title not available (Why is that?)
• Scheduling tasks on a flexible manufacturing machine to minimize tool change delays
• Greedy posets for the bump-minimizing problem
• Title not available (Why is that?)
• Jumps of Orderings
• Minimizing the maximum bump cost in linear extensions of a poset

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)