Approximation algorithms for the interval constrained coloring problem

DOI10.1007/s00453-010-9406-0zbMath1221.68098OpenAlexW2007859145MaRDI QIDQ639285

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

Publication date: 20 September 2011

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsLP roundingcoloring problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Protein sequences, DNA sequences (92D20) Approximation algorithms (68W25)

Related Items (1)

The interval constrained 3-coloring problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs
• Dependent rounding and its applications to approximation algorithms
• Deconstructing Intractability: A Case Study for Interval Constrained Coloring

This page was built for publication: Approximation algorithms for the interval constrained coloring problem