Issue Theoret. Informatics Appl. Volume 39, Number 1, January-March 2005 Imre Simon, the tropical computer scientist Page(s) 133 - 144 DOI 10.1051/ita:2005008

Theoret. Informatics Appl. 39, 133-144 (2005)
DOI: 10.1051/ita:2005008

Finding H-partitions efficiently

Simone Dantas¹, Celina M.H. de Figueiredo², Sylvain Gravier³ and Sulamita Klein<sup>2

1</sup>  Instituto de Computação, Universidade Estadual de Campinas, Caixa Postal 6176, CEP 13084-971, Campinas, SP, Brasil; sdantas@ic.unicamp.br
²  Instituto de Matemática and COPPE, Universidade Federal do Rio de Janeiro, Caixa Postal 68530, CEP 21945-970, Rio de Janeiro, RJ, Brasil; celina@cos.ufrj.br & sula@cos.ufrj.br
³  CNRS, GeoD research group, "Maths à modeler" project, Laboratoire Leibniz, France; sylvain.gravier@imag.fr

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.

Mathematics Subject Classification. 05C85, 68R10

Key words: Structural graph theory -- computational difficulty of problems -- analysis of algorithms and problem complexity -- perfect graphs -- skew partition


© EDP Sciences 2005

What is OpenURL?