Artículos de revistas
Finding H-partitions efficiently
Registro en:
Rairo-theoretical Informatics And Applications. E D P Sciences, v. 39, n. 1, n. 133, n. 144, 2005.
0988-3754
WOS:000228647300009
10.1051/ita:2005008
Autor
Dantas, S
de Figueiredo, CMH
Gravier, S
Klein, S
Institución
Resumen
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. 39 1 133 144