Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/94591
Type: Artigo de periódico
Title: Tree Loop Graphs
Author: Alcon L.
de Figueiredo C.H.
Cerioli M.
Gutierrez M.
Meidanis J.
Abstract: Many problems involving DNA can be modelled by interval families. However, traditional interval graphs do not take into account the repeat structures of a DNA molecule. 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, it produces a loop representation for the tree. © 2004 Elsevier B.V. All rights reserved.
Editor: 
Rights: fechado
Identifier DOI: 10.1016/j.endm.2004.06.003
Address: http://www.scopus.com/inward/record.url?eid=2-s2.0-34247134651&partnerID=40&md5=d704123cff74ac257f9c162f7fbea01f
Date Issue: 2004
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.