An improved approximation ratio for the jump number problem on interval orders
DOI10.1016/J.TCS.2013.10.011zbMATH Open1335.68295OpenAlexW1992481063MaRDI QIDQ391978FDOQ391978
Publication date: 13 January 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2013.10.011
combinatorial optimizationapproximation algorithmset coverposetgraph packinglinear extensioninterval orderjump number
Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorics of partially ordered sets (06A07)
Cites Work
- On the Complexity of General Graph Factor Problems
- Tackling the jump number of interval orders
- Title not available (Why is that?)
- An algorithm for solving the jump number problem
- Packing subgraphs in a graph
- Computing the jump number on semi-orders is polynomial
- The jump number problem on interval orders: A 3/2 approximation algorithm
- Title not available (Why is that?)
- NP-completeness properties about linear extensions
- A 3/2-approximation algorithm for the jump number of interval orders
Cited In (5)
Recommendations
- A refined analysis on the jump number problem of interval orders 👍 👎
- A 3/2-approximation algorithm for the jump number of interval orders 👍 👎
- The jump number problem on interval orders: A 3/2 approximation algorithm 👍 👎
- Title not available (Why is that?) 👍 👎
- Tackling the jump number of interval orders 👍 👎
This page was built for publication: An improved approximation ratio for the jump number problem on interval orders
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q391978)
