ON INTERVALIZING K-COLORED GRAPHS FOR DNA PHYSICAL MAPPING

Authors
BODLAENDER HL DEFLUITER B
Citation
Hl. Bodlaender et B. Defluiter, ON INTERVALIZING K-COLORED GRAPHS FOR DNA PHYSICAL MAPPING, Discrete applied mathematics, 71(1-3), 1996, pp. 55-77
Citations number
19
Categorie Soggetti
Mathematics,Mathematics
Journal title
Discrete applied mathematics → ACNP
Volume
71
Issue
1-3
Year of publication
1996
Pages
55 - 77
Database
ISI
SICI code
Abstract
The problem of determining whether a given k-colored graph is a subgra ph of a properly colored interval graph has an application in DNA phys ical mapping. In this paper, we study the problem for the case that th e number of colors k is fixed. For k = 2, we give a simple linear time algorithm, for k = 3, we give an O(n(2)) algorithm for biconnected gr aphs with n vertices, and for k = 4, we show that the problem is NP-co mplete.