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

Abstract

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

How to cite

top

Dantas, 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. [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. [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. [3] V. Chvátal, Star-Cutsets and Perfect Graphs. J. Combin. Theory Ser. B 39 (1985) 189–199. Zbl0674.05058
  4. [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. [5] T. Feder and P. Hell, List homomorphisms to reflexive graphs. J. Combin. Theory Ser. B 72 (1998) 236–250. Zbl0904.05078
  6. [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. [7] T. Feder, P. Hell, S. Klein and R. Motwani, List Partitions. SIAM J. Discrete Math. 16 (2003) 449–478. Zbl1029.05143

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.