Finding H-partitions efficiently
Dantas, Simone ; de Figueiredo, Celina M. H. ; Gravier, Sylvain ; Klein, Sulamita
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005), p. 133-144 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2005-01-01
DOI : https://doi.org/10.1051/ita:2005008
Classification:  05C85,  68R10 
@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},
     volume = {39},
     year = {2005},
     pages = {133-144},
     doi = {10.1051/ita:2005008},
     mrnumber = {2132583},
     zbl = {1063.05124},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 133-144. doi : 10.1051/ita:2005008. http://gdmltest.u-ga.fr/item/ITA_2005__39_1_133_0/

[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 0674.05058

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

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

[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 1029.05143