A 3/2-approximation algorithm for the jump number of interval orders
From MaRDI portal
Publication:921022
DOI10.1007/BF00346129zbMath0709.06001OpenAlexW2078314359MaRDI QIDQ921022
Publication date: 1990
Published in: Order (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00346129
Related Items (7)
The jump number problem on interval orders: A 3/2 approximation algorithm ⋮ An improved approximation ratio for the jump number problem on interval orders ⋮ The arboreal jump number of an order ⋮ On minimizing jumps for ordered sets ⋮ Tackling the jump number of interval orders ⋮ On a setup optimization problem for interval orders ⋮ A refined analysis on the jump number problem of interval orders
Cites Work
- Minimizing the jump number for partially ordered sets: A graph-theoretic approach
- A setup heuristic for interval orders
- A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders
- On finding the jump number of a partial order by substitution decomposition
- On minimizing the jump number for interval orders
- Optimal Linear Extensions by Interchanging Chains
- Algorithmic Approaches to Setup Minimization
- Minimizing Setups for Cycle-Free Ordered Sets
This page was built for publication: A 3/2-approximation algorithm for the jump number of interval orders