The jump number problem on interval orders: A 3/2 approximation algorithm

DOI10.1016/0012-365X(94)00290-YMaRDI QIDQ1898347zbMATH OpenOpenAlexFDO

Authors Maciej M. Sysło

Publication date 13 May 1996

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(94)00290-y

zbMATH Keywords

approximation algorithmarc-diagram representationinterval ordersjump number

Mathematics Subject Classification ID

Partial orders, general (06A06)

Review text

The paper deals with the jump number problem on interval orders. Using the arc-diagram representation of ordered sets, the author gives an approximation algorithm for this problem. Further he shows a complete characterization of the representation of the interval orders by arc- diagrams.

Recommendations

• An improved approximation ratio for the jump number problem on interval orders
• A 3/2-approximation algorithm for the jump number of interval orders
• A refined analysis on the jump number problem of interval orders
• Tackling the jump number of interval orders
• On a setup optimization problem for interval orders

Cites work

• A 3/2-approximation algorithm for the jump number of interval orders
• A linear-time recognition algorithm for interval dags
• A setup heuristic for interval orders
• An algorithm for solving the jump number problem
• Betweenness, orders and interval graphs
• scientific article; zbMATH DE number 3896963 (Why is no real title available?)
• Minimizing the jump number for partially-ordered sets: A graph-theoretic approach. II
• NP-completeness properties about linear extensions
• On some new types of greedy chains and greedy linear extensions of partially ordered sets
• Scheduling Interval-Ordered Tasks
• Tackling the jump number of interval orders

Cited in

(11)

• Tackling the jump number of interval orders
• On a setup optimization problem for interval orders
• Computing the jump number on semi-orders is polynomial
• Review of properties of different precedence graphs for scheduling problems
• On some new types of greedy chains and greedy linear extensions of partially ordered sets
• The arboreal jump number of an order
• A refined analysis on the jump number problem of interval orders
• scientific article; zbMATH DE number 3948306 (Why is no real title available?)
• An improved approximation ratio for the jump number problem on interval orders
• scientific article; zbMATH DE number 764417 (Why is no real title available?)
• A 3/2-approximation algorithm for the jump number of interval orders

This page was built for publication: The jump number problem on interval orders: A 3/2 approximation algorithm

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