Approximation algorithms for the interval constrained coloring problem

Cite This

Files in this item

Checksum: MD5:0fb723231eed0b4ab3d175eb0b9971b9

ALTHAUS, Ernst, Stefan CANZAR, Khaled ELBASSIONI, Andreas KARRENBAUER, Julián MESTRE, 2010. Approximation algorithms for the interval constrained coloring problem. In: Algorithmica. 61(2), pp. 342-361. ISSN 0178-4617. Available under: doi: 10.1007/s00453-010-9406-0

@article{Althaus2010Appro-17265, title={Approximation algorithms for the interval constrained coloring problem}, year={2010}, doi={10.1007/s00453-010-9406-0}, number={2}, volume={61}, issn={0178-4617}, journal={Algorithmica}, pages={342--361}, author={Althaus, Ernst and Canzar, Stefan and Elbassioni, Khaled and Karrenbauer, Andreas and Mestre, Julián} }

<rdf:RDF xmlns:dcterms="" xmlns:dc="" xmlns:rdf="" xmlns:bibo="" xmlns:dspace="" xmlns:foaf="" xmlns:void="" xmlns:xsd="" > <rdf:Description rdf:about=""> <dcterms:title>Approximation algorithms for the interval constrained coloring problem</dcterms:title> <dc:creator>Canzar, Stefan</dc:creator> <dc:creator>Mestre, Julián</dc:creator> <dc:language>eng</dc:language> <dcterms:isPartOf rdf:resource=""/> <dcterms:issued>2010</dcterms:issued> <dc:contributor>Mestre, Julián</dc:contributor> <dc:contributor>Karrenbauer, Andreas</dc:contributor> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dspace:isPartOfCollection rdf:resource=""/> <dc:contributor>Althaus, Ernst</dc:contributor> <dc:contributor>Canzar, Stefan</dc:contributor> <dcterms:hasPart rdf:resource=""/> <dcterms:abstract xml:lang="eng">We consider the interval constrained coloring problem, which appears in the interpretation of experimental data in biochemistry. Monitoring hydrogendeuterium exchange rates via mass spectroscopy experiments is a method used to obtain information about protein tertiary structure. The output of these experiments provides data about the exchange rate of residues in overlapping segments of the protein backbone. These segments must be re-assembled in order to obtain a global picture of the protein structure. The interval constrained coloring problem is the mathematical abstraction of this re-assembly process. The objective of the interval constrained coloring problem is to assign a color (exchange rate) to a set of integers (protein residues) such that a set of constraints is satisfied. Each constraint is made up of a closed interval (protein segment) and requirements on the number of elements that belong to each color class (exchange rates observed in the experiments).</dcterms:abstract> <dc:date rdf:datatype="">2011-12-01T12:41:29Z</dc:date> <dc:rights>terms-of-use</dc:rights> <dc:creator>Elbassioni, Khaled</dc:creator> <dcterms:bibliographicCitation>First publ. in: Algorithmica ; 61 (2011), 2. - S. 342-361</dcterms:bibliographicCitation> <dcterms:rights rdf:resource=""/> <dc:creator>Althaus, Ernst</dc:creator> <dspace:isPartOfCollection rdf:resource=""/> <dc:creator>Karrenbauer, Andreas</dc:creator> <dspace:hasBitstream rdf:resource=""/> <dc:contributor>Elbassioni, Khaled</dc:contributor> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:isPartOf rdf:resource=""/> <dcterms:available rdf:datatype="">2011-12-01T12:41:29Z</dcterms:available> <bibo:uri rdf:resource=""/> </rdf:Description> </rdf:RDF>

Downloads since Oct 1, 2014 (Information about access statistics)

Karrenbauer etal.pdf 967

This item appears in the following Collection(s)

Search KOPS


My Account