Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/66964
Type: Artigo de periódico
Title: Finding H-partitions efficiently
Author: Dantas, S
de Figueiredo, CMH
Gravier, S
Klein, S
Abstract: We study the concept of an H-partition of the vertex set of a graph G, which includes all vertex partitioning problems into four parts which we require to be nonempty with only external constraints according to the structure of a model graph H, with the exception of two cases, one that has already been classified as polynomial, and the other one remains unclassified. In the context of more general vertex-partition problems, the problems addressed in this paper have these properties: non-list, 4-part, external constraints only ( no internal constraints), each part non-empty. We describe tools that yield for each problem considered in this paper a simple and low complexity polynomial-time algorithm.
Subject: structural graph theory
computational difficulty of problems
analysis of algorithms and problem complexity
perfect graphs
skew partition
Country: França
Editor: E D P Sciences
Rights: aberto
Identifier DOI: 10.1051/ita:2005008
Date Issue: 2005
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.