# Finding $H$-partitions efficiently

Simone Dantas; Celina M. H. de Figueiredo; Sylvain Gravier; Sulamita Klein

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2005)

- Volume: 39, Issue: 1, page 133-144
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topDantas, Simone, et al. "Finding $H$-partitions efficiently." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 39.1 (2005): 133-144. <http://eudml.org/doc/245565>.

@article{Dantas2005,

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.},

author = {Dantas, Simone, de Figueiredo, Celina M. H., Gravier, Sylvain, Klein, Sulamita},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {structural graph theory; computational difficulty of problems; analysis of algorithms and problem complexity; perfect graphs; skew partition; list partition; efficient algorithm},

language = {eng},

number = {1},

pages = {133-144},

publisher = {EDP-Sciences},

title = {Finding $H$-partitions efficiently},

url = {http://eudml.org/doc/245565},

volume = {39},

year = {2005},

}

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

PB - EDP-Sciences

VL - 39

IS - 1

SP - 133

EP - 144

AB - 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.

LA - eng

KW - structural graph theory; computational difficulty of problems; analysis of algorithms and problem complexity; perfect graphs; skew partition; list partition; efficient algorithm

UR - http://eudml.org/doc/245565

ER -

## References

top- [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. Zbl1318.05072
- [2] M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, Strong Perfect Graph Theorem, in Perfect Graph Conjecture workshop. American Institute of Mathematics (2002). Zbl1112.05042
- [3] V. Chvátal, Star-Cutsets and Perfect Graphs. J. Combin. Theory Ser. B 39 (1985) 189–199. Zbl0674.05058
- [4] C.M.H. de Figueiredo, S. Klein, Y. Kohayakawa and B. Reed, Finding Skew Partitions Efficiently. J. Algorithms 37 (2000) 505–521. Zbl0964.68107
- [5] T. Feder and P. Hell, List homomorphisms to reflexive graphs. J. Combin. Theory Ser. B 72 (1998) 236–250. Zbl0904.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. Zbl1029.05143

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.