Projet d'Etude et Recherche 2014

Olivier Baudon (olivier.baudon@labri.fr) et Julien Bensmail (julien.bensmail@labri.fr)

L'objet de ce projet est l'étude d'un article de Ma Jun et Ma Shaohan, "An O(k2n2) Algorithm to Find a k-Partition in a k-Connected Graph"[MM94].

En 1977, Gyŏri [Gyö78] et et Lovász [Lov77] ont prouvé indépendamment que, pour tout graphe G non orienté à n sommets et k-connexe, toute suite v1, ..., vk de k sommets de G et toute suite n1, ..., nk de k entiers telle que n1+ ... + nk = n, il était possible de trouver une partition V1, ..., Vk de l'ensemble V des sommets de G telle que pour tout 1 ≤ i ≤ k, |Vi| = ni, vi Vi .et G[Vi] connexe, où G[Vi] désigne le sous-graphe de G induit par Vi.
Les preuves de Gyŏri et et Lovász ne sont pas constructives. Suite à leurs articles, quelques algorithmes ont été proposés, pour de petites valeurs de k et parfois des classes de graphes particulières (graphes planaires) [MNTU90, NSRN97, STN90]. L'article à étudier propose lui un algorithme général pour calculer une telle partition.
L'objectif du projet est de bien comprendre l'algorithme (en le programmant) ainsi que les preuves d'exactitude et de complexité. Selon le niveau d'avancement, il pourra être envisagé de programmer un autre algorithme de Nagamochi et Ibaraki [NI92], nécessaire à l'obtention de la complexité optimale.

Bibliographie

[Gyö78] E. Györi. On division of graphs to connected subgraphs. In Colloq. Math. Soc. János Bolyai, volume 18, pages 485–494. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976, Vol.I), 1978.

[Lov77] L. Lovász. A homology theory for spanning trees of a graph. Acta Mathematica Academiae Scientiarum Hungaricae, 30(3-4):241–251, 1977.

[MM94] J. Ma and S.H. Ma. An O(k2n2) algorithm to find a k-partition in a k-connected graph. Journal of Computer Science and Technology, 9(1):86–91, 1994.

[MNTU90] T.H. Miyano, T. Nishizeki, N. Takahashi, and S. Uneo. An algorithm for tripartioning 3-connected graphs. J. Inform. Proc. Society of Japan, 1990. (in Japanese).

[NI92] Nagamochi H, Ibaraki T. A linear-time algorithm for finding a Sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 1992, 7: 583-596.

[NSRN97] S. Nakano, M. Saidur Rahman, and T. Nishizeki. A linear time algorithm for four partitioning four-connected planar graphs. Information Processing Letters, 62(6):315–322, 1997.

[STN90] H. Suzuki, N. Takahashi, and T. Nishizeki. A linear algorithm for bipartition of biconnected graphs. Information Processing Letters, 33:227–231, 1990.