On the approximability of the maximum interval constrained coloring problem

DOI10.1016/j.disopt.2017.09.002zbMath1506.68180OpenAlexW2966104185MaRDI QIDQ1662109

Stefan Canzar, Amr Elmasry, Rajiv Raman, Khaled M. Elbassioni

Publication date: 17 August 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2017.09.002

zbMATH Keywords

dynamic programmingpartially ordered setapproximation algorithmsprotein structureAPX-hardnessinterval-constrained coloring

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Protein sequences, DNA sequences (92D20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (1)

The maximum feasible subset problem (maxFS) and applications

Cites Work

• Unnamed Item
• The subchromatic number of a graph
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A decomposition theorem for partially ordered sets
• On the Approximability of the Maximum Interval Constrained Coloring Problem
• Approximating the Interval Constrained Coloring Problem
• On a graph coloring problem arising from discrete tomography
• Deconstructing Intractability: A Case Study for Interval Constrained Coloring
• A polynomial-delay algorithm for enumerating approximate solutions to the interval constrained coloring problem
• Some optimal inapproximability results
• On the use of graphs in discrete tomography

This page was built for publication: On the approximability of the maximum interval constrained coloring problem