Please use this identifier to cite or link to this item:
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.
Rights: fechado
Identifier DOI: 10.1016/j.endm.2004.06.003
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.