# Finding H-partitions efficiently

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

RAIRO - Theoretical Informatics and Applications (2010)

- 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 39.1 (2010): 133-144. <http://eudml.org/doc/92751>.

@article{Dantas2010,

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

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

language = {eng},

month = {3},

number = {1},

pages = {133-144},

publisher = {EDP Sciences},

title = {Finding H-partitions efficiently},

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

volume = {39},

year = {2010},

}

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

DA - 2010/3//

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/92751

ER -

## References

top- 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.
- M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, Strong Perfect Graph Theorem, in Perfect Graph Conjecture workshop. American Institute of Mathematics (2002).
- V. Chvátal, Star-Cutsets and Perfect Graphs. J. Combin. Theory Ser. B39 (1985) 189–199.
- C.M.H. de Figueiredo, S. Klein, Y. Kohayakawa and B. Reed, Finding Skew Partitions Efficiently. J. Algorithms37 (2000) 505–521.
- T. Feder and P. Hell, List homomorphisms to reflexive graphs. J. Combin. Theory Ser. B72 (1998) 236–250.
- 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.
- T. Feder, P. Hell, S. Klein and R. Motwani, List Partitions. SIAM J. Discrete Math.16 (2003) 449–478.

## NotesEmbed ?

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