Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Approximation Algorithms for the Interval Constrained Coloring Problem
 
research article

Approximation Algorithms for the Interval Constrained Coloring Problem

Althaus, Ernst
•
Canzar, Stefan
•
Elbassioni, Khaled
Show more
2011
Algorithmica

We consider the interval constrained coloring problem, which appears in the interpretation of experimental data in biochemistry. Monitoring hydrogen-deuterium 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.

  • Details
  • Metrics
Type
research article
DOI
10.1007/s00453-010-9406-0
Web of Science ID

WOS:000293234800006

Author(s)
Althaus, Ernst
Canzar, Stefan
Elbassioni, Khaled
Karrenbauer, Andreas
Mestre, Julian
Date Issued

2011

Published in
Algorithmica
Volume

61

Start page

342

End page

361

Subjects

Approximation algorithms

•

Coloring problems

•

LP rounding

Editorial or Peer reviewed

REVIEWED

Written at

OTHER

EPFL units
DISOPT  
Available on Infoscience
December 16, 2011
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/73786
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés