Tree loop graphs

dc.creatorAlcon, L
dc.creatorCerioli, MR
dc.creatorde Figueiredo, CMH
dc.creatorGutierrez, M
dc.creatorMeidanis, J
dc.date2007
dc.dateAPR 1
dc.date2014-11-13T18:36:20Z
dc.date2015-11-26T17:11:00Z
dc.date2014-11-13T18:36:20Z
dc.date2015-11-26T17:11:00Z
dc.date.accessioned2018-03-28T23:59:33Z
dc.date.available2018-03-28T23:59:33Z
dc.identifierDiscrete Applied Mathematics. Elsevier Science Bv, v. 155, n. 41826, n. 686, n. 694, 2007.
dc.identifier0166-218X
dc.identifierWOS:000245794600003
dc.identifier10.1016/j.dam.2005.01.001
dc.identifierhttp://www.repositorio.unicamp.br/jspui/handle/REPOSIP/77370
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/77370
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/77370
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1280998
dc.descriptionMany problems involving DNA can be modeled by families of intervals. However, traditional interval graphs do not take into account the repeat structure of a DNA molecule. In the simplest case, one repeat with two copies, the underlying line can be seen as folded into a loop. We propose a new definition that respects repeats and define loop graphs as the intersection graphs of arcs of a loop. The class of loop graphs contains the class of interval graphs and the class of circular-arc graphs. Every loop graph has interval number 2. We characterize the trees that are loop graphs. The characterization yields a polynomial-time algorithm which given a tree decides whether it is a loop graph and. in the affirmative case. produces it loop representation for the tree. (c) 2006 Elsevier B.V. All rights reserved.
dc.description155
dc.description41826
dc.description686
dc.description694
dc.languageen
dc.publisherElsevier Science Bv
dc.publisherAmsterdam
dc.publisherHolanda
dc.relationDiscrete Applied Mathematics
dc.relationDiscret Appl. Math.
dc.rightsfechado
dc.rightshttp://www.elsevier.com/about/open-access/open-access-policies/article-posting-policy
dc.sourceWeb of Science
dc.subjectinterval graphs
dc.subjectinterval number
dc.subjectcomputational molecular biology
dc.subjectDNA fragment assembly problem
dc.subjectDNA physical mapping
dc.subjectInterval Graphs
dc.subjectNumber
dc.titleTree loop graphs
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución