Finding -partitions efficiently
Simone Dantas, Celina M. H. de Figueiredo, Sylvain Gravier, Sulamita Klein (2005)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We study the concept of an -partition of the vertex set of a graph , 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 , 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:...