The jump number problem on interval orders: A 3/2 approximation algorithm
From MaRDI portal
Publication:1898347
DOI10.1016/0012-365X(94)00290-YzbMath0837.06002OpenAlexW1981163443MaRDI QIDQ1898347
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
Related Items (5)
On some new types of greedy chains and greedy linear extensions of partially ordered sets ⋮ An improved approximation ratio for the jump number problem on interval orders ⋮ The arboreal jump number of an order ⋮ Review of properties of different precedence graphs for scheduling problems ⋮ A refined analysis on the jump number problem of interval orders
Cites Work
- NP-completeness properties about linear extensions
- A 3/2-approximation algorithm for the jump number of interval orders
- A setup heuristic for interval orders
- Minimizing the jump number for partially-ordered sets: A graph-theoretic approach. II
- An algorithm for solving the jump number problem
- A linear-time recognition algorithm for interval dags
- Tackling the jump number of interval orders
- On some new types of greedy chains and greedy linear extensions of partially ordered sets
- Betweenness, orders and interval graphs
- Scheduling Interval-Ordered Tasks
- Unnamed Item
This page was built for publication: The jump number problem on interval orders: A 3/2 approximation algorithm
