Busca avançada
Ano de início
Entree


Minimal separators in extended P-4-laden graphs

Texto completo
Autor(es):
Pedrotti, Vagner ; de Mello, Celia Picinin
Número total de Autores: 2
Tipo de documento: Artigo Científico
Fonte: DISCRETE APPLIED MATHEMATICS; v. 160, n. 18, p. 9-pg., 2012-12-01.
Resumo

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. (AU)

Processo FAPESP: 07/58519-0 - Aplicações da decomposição modular em grafos
Beneficiário:Vagner Pedrotti
Modalidade de apoio: Bolsas no Brasil - Doutorado