Geodesic
Finding H-partitions efficiently
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 1, pp. 133-144

Voir la notice de l'article provenant de la source Numdam

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.

DOI : 10.1051/ita:2005008
Classification : 05C85, 68R10
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 :