A refined analysis on the jump number problem of interval orders

DOI10.1016/J.IPL.2015.06.002MaRDI QIDQ2353641zbMATHOpenAlexFDO

Authors Chen Yuan, Haibin Kan

Publication date 15 July 2015

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

Full work available at URL https://doi.org/10.1016/j.ipl.2015.06.002

zbMATH Keywords

approximation algorithmsinterval orderjump number

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorics of partially ordered sets (06A07)

Recommendations

• An improved approximation ratio for the jump number problem on interval orders
• Tackling the jump number of interval orders
• A tabu search approach to the jump number problem
• The jump number problem on interval orders: A 3/2 approximation algorithm
• Computing the jump number on semi-orders is polynomial

Cites work

• scientific article; zbMATH DE number 3877239 (Why is no real title available?)
• A 3/2-approximation algorithm for the jump number of interval orders
• An improved approximation ratio for the jump number problem on interval orders
• NP-completeness properties about linear extensions
• Packing subgraphs in a graph
• Tackling the jump number of interval orders
• The jump number problem on interval orders: A 3/2 approximation algorithm

Cited in

(7)

• The jump number problem on interval orders: A 3/2 approximation algorithm
• A weighted version of the jump number problem on two-dimensional orders is NP-complete
• An improved approximation ratio for the jump number problem on interval orders
• scientific article; zbMATH DE number 1558370 (Why is no real title available?)
• An improved algorithm for the jump number problem
• Jumps of Orderings
• Computing the jump number on semi-orders is polynomial

This page was built for publication: A refined analysis on the jump number problem of interval orders

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