Approximating the Interval Constrained Coloring Problem

DOI10.1007/978-3-540-69903-3_20zbMath1155.68573OpenAlexW2130618484MaRDI QIDQ3512460

Julián Mestre, Ernst Althaus, Andreas Karrenbauer, Stefan Canzar, Khaled M. Elbassioni

Publication date: 15 July 2008

Published in: Algorithm Theory – SWAT 2008 (Search for Journal in Brave)

Full work available at URL: http://nbn-resolving.de/urn:nbn:de:bsz:352-opus-121999

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Biochemistry, molecular biology (92C40) Approximation algorithms (68W25)

Related Items (5)

On the approximability of the maximum interval constrained coloring problem ⋮ The interval constrained 3-coloring problem ⋮ Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring ⋮ Upper and lower bounds for finding connected motifs in vertex-colored graphs ⋮ Deconstructing Intractability: A Case Study for Interval Constrained Coloring

Cites Work

• A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs
• Dependent rounding and its applications to approximation algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximating the Interval Constrained Coloring Problem