A refined analysis on the jump number problem of interval orders

DOI10.1016/J.IPL.2015.06.002zbMATH Open1332.68289OpenAlexW562997672MaRDI QIDQ2353641FDOQ2353641

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

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

zbMATH Keywords

approximation algorithmsinterval orderjump number

Mathematics Subject Classification ID

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

Cites Work

• Tackling the jump number of interval orders
• Title not available (Why is that?)
• Packing subgraphs in a graph
• The jump number problem on interval orders: A 3/2 approximation algorithm
• An improved approximation ratio for the jump number problem on interval orders
• NP-completeness properties about linear extensions
• A 3/2-approximation algorithm for the jump number of interval orders

Cited In (7)

• An improved approximation ratio for the jump number problem on interval orders
• A weighted version of the jump number problem on two-dimensional orders is NP-complete
• Computing the jump number on semi-orders is polynomial
• The jump number problem on interval orders: A 3/2 approximation algorithm
• An improved algorithm for the jump number problem
• Title not available (Why is that?)
• Jumps of Orderings

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)