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

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
Mots-clés : 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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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. http://archive.numdam.org/articles/10.1051/ita:2005008/

[1] K. Cameron, E.M. Eschen, C.T. Hoàng and R. Sritharan, The list partition problem for graphs, in Proc. of the ACM-SIAM Symposium on Discrete Algorithms - SODA 2004. ACM, New York and SIAM, Philadelphia (2004) 384-392.

[2] M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, Strong Perfect Graph Theorem, in Perfect Graph Conjecture workshop. American Institute of Mathematics (2002).

[3] V. Chvátal, Star-Cutsets and Perfect Graphs. J. Combin. Theory Ser. B 39 (1985) 189-199. | Zbl

[4] C.M.H. De Figueiredo, S. Klein, Y. Kohayakawa and B. Reed, Finding Skew Partitions Efficiently. J. Algorithms 37 (2000) 505-521. | Zbl

[5] T. Feder and P. Hell, List homomorphisms to reflexive graphs. J. Combin. Theory Ser. B 72 (1998) 236-250. | Zbl

[6] T. Feder, P. Hell, S. Klein and R. Motwani, Complexity of graph partition problems, in Proc. of the 31st Annual ACM Symposium on Theory of Computing - STOC'99. Plenum Press, New York (1999) 464-472.

[7] T. Feder, P. Hell, S. Klein and R. Motwani, List Partitions. SIAM J. Discrete Math. 16 (2003) 449-478. | Zbl

Cité par Sources :