Approximating the Interval Constrained Coloring Problem

DOI10.1007/978-3-540-69903-3_20MaRDI QIDQ3512460zbMATH OpenOpenAlexFDO

Authors Ernst Althaus, Stefan Canzar, Andreas Karrenbauer, Julián Mestre, Khaled 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

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

Recommendations

• Approximation algorithms for the interval constrained coloring problem
• On the approximability of the maximum interval constrained coloring problem
• On the approximability of the maximum interval constrained coloring problem
• A polynomial delay algorithm for enumerating approximate solutions to the interval constrained coloring problem
• A polynomial-delay algorithm for enumerating approximate solutions to the interval constrained coloring problem

Cites work

• scientific article; zbMATH DE number 5764814 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2081005 (Why is no real title available?)
• A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs
• Dependent rounding and its applications to approximation algorithms

Cited in

(12)

• On the approximability of the maximum interval constrained coloring problem
• Approximation Algorithms for Bounded Color Matchings via Convex Decompositions
• Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring
• On the approximability of the maximum interval constrained coloring problem
• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• A polynomial delay algorithm for enumerating approximate solutions to the interval constrained coloring problem
• Deconstructing Intractability: A Case Study for Interval Constrained Coloring
• More reliable protein NMR peak assignment via improved 2-interval scheduling
• A polynomial-delay algorithm for enumerating approximate solutions to the interval constrained coloring problem
• The interval constrained 3-coloring problem
• Approximation algorithms for the interval constrained coloring problem
• Conditional Hardness for Approximate Coloring

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3512460)