On a setup optimization problem for interval orders

DOI10.1016/0020-0190(92)90255-TzbMath0764.68133OpenAlexW1995606789MaRDI QIDQ1195865

Ahmad H. Sharary, Nejib Zaguia

Publication date: 4 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90255-t

zbMATH Keywords

cyclesinterval ordersmaximum clique problemjump number problem

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (2)

On minimizing jumps for ordered sets ⋮ The jump number of Z-free ordered sets

Cites Work

• NP-completeness properties about linear extensions
• Minimizing setups in ordered sets of fixed width
• A 3/2-approximation algorithm for the jump number of interval orders
• A setup heuristic for interval orders
• A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders
• Tackling the jump number of interval orders
• Optimal Linear Extensions by Interchanging Chains
• Minimizing Setups for Cycle-Free Ordered Sets

This page was built for publication: On a setup optimization problem for interval orders