dc.creator | Ferreira, CE | |
dc.creator | de Souza, CC | |
dc.creator | Wakabayashi, Y | |
dc.date | 2002 | |
dc.date | 42005 | |
dc.date | 2014-11-18T16:02:58Z | |
dc.date | 2015-11-26T16:56:34Z | |
dc.date | 2014-11-18T16:02:58Z | |
dc.date | 2015-11-26T16:56:34Z | |
dc.date.accessioned | 2018-03-28T23:44:00Z | |
dc.date.available | 2018-03-28T23:44:00Z | |
dc.identifier | Discrete Applied Mathematics. Elsevier Science Bv, v. 116, n. 41671, n. 161, n. 177, 2002. | |
dc.identifier | 0166-218X | |
dc.identifier | WOS:000173568800010 | |
dc.identifier | 10.1016/S0166-218X(00)00324-3 | |
dc.identifier | http://www.repositorio.unicamp.br/jspui/handle/REPOSIP/80602 | |
dc.identifier | http://www.repositorio.unicamp.br/handle/REPOSIP/80602 | |
dc.identifier | http://repositorio.unicamp.br/jspui/handle/REPOSIP/80602 | |
dc.identifier.uri | http://repositorioslatinoamericanos.uchile.cl/handle/2250/1277413 | |
dc.description | We consider a problem called minimum k-contig problem (MkCP), whose specialization to an alphabet with four symbols can be seen as a problem that arises in the process of arranging DNA fragments to reconstruct a molecule. We present a graph theoretical formulation of MkCP and mention some extensions. We show this problem to be NP-hard for every k greater than or equal to 1 (for an alphabet that is not of fixed cardinality). A 0/1 integer linear programming formulation of the problem is given and some results of a branch-and-cut algorithm based on this formulation are discussed. (C) 2002 Elsevier Science B.V. All rights reserved. | |
dc.description | 116 | |
dc.description | 41671 | |
dc.description | 161 | |
dc.description | 177 | |
dc.language | en | |
dc.publisher | Elsevier Science Bv | |
dc.publisher | Amsterdam | |
dc.publisher | Holanda | |
dc.relation | Discrete Applied Mathematics | |
dc.relation | Discret Appl. Math. | |
dc.rights | fechado | |
dc.rights | http://www.elsevier.com/about/open-access/open-access-policies/article-posting-policy | |
dc.source | Web of Science | |
dc.subject | integer programming | |
dc.subject | computational biology | |
dc.subject | branch-and-cut | |
dc.subject | polyhedral combinatorics | |
dc.title | Rearrangement of DNA fragments: a branch-and-cut algorithms | |
dc.type | Artículos de revistas | |