An improved approximation ratio for the jump number problem on interval orders

DOI10.1016/j.tcs.2013.10.011zbMath1335.68295OpenAlexW1992481063MaRDI QIDQ391978

Przemysław Krysztowiak

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

zbMATH Keywords

posetcombinatorial optimizationapproximation algorithminterval orderjump numberset covergraph packinglinear extension

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (1)

A refined analysis on the jump number problem of interval orders

Cites Work

• Unnamed Item
• Unnamed Item
• NP-completeness properties about linear extensions
• A 3/2-approximation algorithm for the jump number of interval orders
• An algorithm for solving the jump number problem
• Packing subgraphs in a graph
• Tackling the jump number of interval orders
• Computing the jump number on semi-orders is polynomial
• The jump number problem on interval orders: A 3/2 approximation algorithm
• On the Complexity of General Graph Factor Problems

This page was built for publication: An improved approximation ratio for the jump number problem on interval orders