dc.creator | Ferreira C.E. | |
dc.creator | De Souza C.C. | |
dc.creator | Wakabayashi Y. | |
dc.date | 2002 | |
dc.date | 2015-06-30T16:44:35Z | |
dc.date | 2015-11-26T15:36:39Z | |
dc.date | 2015-06-30T16:44:35Z | |
dc.date | 2015-11-26T15:36:39Z | |
dc.date.accessioned | 2018-03-28T22:45:07Z | |
dc.date.available | 2018-03-28T22:45:07Z | |
dc.identifier | | |
dc.identifier | Discrete Applied Mathematics. , v. 116, n. 1-2, p. 161 - 177, 2002. | |
dc.identifier | 0166218X | |
dc.identifier | 10.1016/S0166-218X(00)00324-3 | |
dc.identifier | http://www.scopus.com/inward/record.url?eid=2-s2.0-84867932002&partnerID=40&md5=8e0e67c9b0c97adbe144fece6c27d4de | |
dc.identifier | http://www.repositorio.unicamp.br/handle/REPOSIP/101869 | |
dc.identifier | http://repositorio.unicamp.br/jspui/handle/REPOSIP/101869 | |
dc.identifier | 2-s2.0-84867932002 | |
dc.identifier.uri | http://repositorioslatinoamericanos.uchile.cl/handle/2250/1263480 | |
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 ke;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. © 2002 Elsevier Science B.V. | |
dc.description | 116 | |
dc.description | 1-2 | |
dc.description | 161 | |
dc.description | 177 | |
dc.description | Crowder, H., Padberg, M.W., Solving large-scale symmetric traveling salesman problems to optimality (1980) Management Sci., 26, pp. 495-509 | |
dc.description | Garey, M.R., Johnson, D.S., (1979) Computer and Intractability - A Guide to the Theory of NP-Completeness, , Freeman New York | |
dc.description | Grötschel, M., Lovász, L., Schrijver, A., (1988) Geometric Algorithms and Combinatorial Optimization, , Springer Berlin | |
dc.description | Kececioglu, J.D., (1991) Exact and Approximation Algorithms for DNA Sequence Reconstruction, , Ph.D. Thesis, University of Arizona, Tucson | |
dc.description | Kececioglu, J.D., Myers, E.W., Combinatorial algorithms for DNA sequence assembly (1995) Algorithmica, 13, pp. 7-51 | |
dc.description | Meidanis, J., (1992) Algorithms for Problems in Computational Genetics, , Ph.D. Thesis, University of Wisconsin, Madison | |
dc.description | Meidanis, J., Setubal, J.C., (1997) Computational Molecular Biology, , PWS Publishing Company Boston | |
dc.description | Padberg, M.W., Grötschel, M., Polyhedral aspects of the travelling salesman problem II: Computations (1985) The Travelling Salesman Problem, , E.L. Lawler, J.K. Lenstra, A.H.G. Rinooy Kan, Wiley New York | |
dc.description | Siegel, A.F., Roach, J.C., Magness, C., Thayer, E., Van Den Engh, G., Optimization of restriction fragment DNA mapping (1998) Journal of Computational Biology, 5 (1), pp. 113-126 | |
dc.language | en | |
dc.publisher | | |
dc.relation | Discrete Applied Mathematics | |
dc.rights | fechado | |
dc.source | Scopus | |
dc.title | Rearrangement Of Dna Fragments: A Branch-and-cut Algorithm | |
dc.type | Artículos de revistas | |