Approximating the Interval Constrained Coloring Problem

DOI10.1007/978-3-540-69903-3_20zbMATH Open1155.68573OpenAlexW2130618484MaRDI QIDQ3512460FDOQ3512460

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Dependent rounding and its applications to approximation algorithms
• A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs
• Title not available (Why is that?)

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)