Voir la notice de l'article provenant de la source Numdam
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: non-list, -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.
Keywords: structural graph theory, computational difficulty of problems, analysis of algorithms and problem complexity, perfect graphs, skew partition
@article{ITA_2005__39_1_133_0,
author = {Dantas, Simone and de Figueiredo, Celina M. H. and Gravier, Sylvain and Klein, Sulamita},
title = {Finding $H$-partitions efficiently},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {133--144},
publisher = {EDP-Sciences},
volume = {39},
number = {1},
year = {2005},
doi = {10.1051/ita:2005008},
mrnumber = {2132583},
zbl = {1063.05124},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2005008/}
}
TY - JOUR AU - Dantas, Simone AU - de Figueiredo, Celina M. H. AU - Gravier, Sylvain AU - Klein, Sulamita TI - Finding $H$-partitions efficiently JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2005 SP - 133 EP - 144 VL - 39 IS - 1 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita:2005008/ DO - 10.1051/ita:2005008 LA - en ID - ITA_2005__39_1_133_0 ER -
%0 Journal Article %A Dantas, Simone %A de Figueiredo, Celina M. H. %A Gravier, Sylvain %A Klein, Sulamita %T Finding $H$-partitions efficiently %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2005 %P 133-144 %V 39 %N 1 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita:2005008/ %R 10.1051/ita:2005008 %G en %F ITA_2005__39_1_133_0
Dantas, Simone; de Figueiredo, Celina M. H.; Gravier, Sylvain; Klein, Sulamita. Finding $H$-partitions efficiently. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 1, pp. 133-144. doi: 10.1051/ita:2005008
Cité par Sources :