Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/57014
Type: Artigo de periódico
Title: Minimal separators in extended P-4-laden graphs
Author: Pedrotti, V
de Mello, CP
Abstract: In this paper, we use the primeval decomposition tree to compute the minimal separators of some graphs and to describe a linear-time algorithm that lists the minimal separators of extended P-4-laden graphs, extending an algorithm for P-4-sparse graphs given by Nikolopoulos and Palios [S.D. Nikolopoulos, L Palios, Minimal separators in P-4-sparse graphs, Discrete Math. 306 (3) (2006) 381-392]. We also give bounds on the number and total size of all minimal separators of extended P-4-laden graphs and some of their subclasses, such as P-4-tidy and P-4-lite graphs. Moreover, we show that these bounds are tight for all subclasses considered. (C) 2012 Elsevier B.V. All rights reserved.
Subject: Minimal separators
Primeval decomposition
Modular decomposition
Graphs with few P-4's
Linear-time algorithms
Country: Holanda
Editor: Elsevier Science Bv
Rights: fechado
Identifier DOI: 10.1016/j.dam.2012.01.025
Date Issue: 2012
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000310667700027.pdf241.94 kBAdobe PDFView/Open


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