JGA 2012

Programme

Mercredi 14 Novembre

10h00 - 11h00: Accueil participants

11h00 - 12h15

11h00 - 11h25:

  • David Cattanéo et Simon Perdrix
  • Etude de la Complexité Paramétrique de Problèmes de Domination et Application aux Codes Linéaires

11h25 - 11h50:

  • Florent Foucaud, Adrian Kosowski, George Mertzios, Reza Naserasr, Aline Parreau et Petru Valicov
  • Quelques résultats de complexité pour les codes identifiants dans les graphes

11h50 - 12h15:

  • Valentin Garnero et Ignasi Sau
  • La Domination Totale admet un noyau linéaire dans les graphes planaires

13h00 - 14h00: Repas

14h00 - 15h00 (Exposé Invité)

Martine Labbé

15h00 - 16h00

15h00 - 15h20:

  • Julio Araujo , Grégory Morel, Leonardo Sampaio, Ronan Soares et Valentin Weber
  • Nombre enveloppe des graphes sans P5 et des régles de réduction

15h20 - 15h40:

  • Jean-François Couturier, Pinar Heggernes, Pim van't Hof et Yngve Villanger
  • Nombre maximum d'ensembles coupe cycles dans un graphe cordal ou un co-graphe

15h40 - 16h20: Pause

16h20 - 18h00

16h20 - 16h40

  • Valentin Borozan, Leandro Montero et Narayanan Narayanan
  • Further results on strong edge colouring

16h40 - 17h00

  • Boris Albar et Daniel Gonçalves
  • Coloration des graphes sans K7 et K8 mineurs

17h00 - 17h20

  • Marthe Bonamy et Nicolas Bousquet
  • Recoloration des graphes d'arborescence bornée

17h20 - 17h40

  • Stéphane Bessy et Nicolas Bousquet
  • Coloration arc-en-ciel pour les graphes 3-chromatique

17h40 - 18h00

  • Maria Chudnovsky, Nicolas Trotignon, Théophile Trunck et Kristina Vu\v skovi\'c
  • Un algorithme polynomial pour colorier les graphes de Berge sans skew-partition

Jeudi 15 Novembre

09h00 - 10h00

09h00 - 09h20

  • Clément Charpentier et Eric Sopena
  • Jeu de coloration d'incidences

09h20 - 09h40

  • Houcine Boumediene Merouane, Mustapha Chellali, Hamamache Kheddouci et Mohammed Haddad
  • Coloration Dominée des graphes

09h40 - 10h00

  • Aline Parreau
  • Coloration localement identifiante

10h00 - 11h00 (Exposé Invité)

Nicolas Trotignon

11h00 - 11h30: Pause

11h30 - 12h50

11h30 - 11h50

  • Daniele Catanzaro, Martine Labbé et Bjarni V. Halld\'orsson
  • A Mixed Integer Programming Model for the Parsimonious Loss of Heterozygosity Problem

11h50 - 12h10

  • Nicolas Bousquet, Aurélie Lagoutte et Stéphan Thomassé
  • Quasi P versus P

12h10 - 12h30

  • Richard Nowakowski et Gabriel Renault
  • Le jeu de Timber

12h30 - 12h50

  • Jean-Alexandre Anglès d'Auriac et Yannis Mannousakis
  • Étude d'un jeu dans un graphe

13h00 - 14h00: Repas

14h00 - 16h00

14h00 - 14h20

  • Christophe Crespelle, Matthieu Latapy et Thi Ha Duong Phan
  • Convergence de quelques opérateurs sur les bicliques d'un graphe multiparti

14h20 - 14h40

  • Nour el islem Karabadji
  • Découverte des sous graphes fréquents

14h40 - 15h00

  • Julien Bensmail
  • Complexité du problème de partitionnement d'un graphe en sous-graphes connexes

15h00 - 15h20

  • F. Giroire, D. Mazauric, N. Nisse, S. Pérennes et R. P. Soares
  • Online Surveillance Number and Connectivity

15h20 - 15h40

  • Jean-Claude Bermond, Bi Li, Nicolas Nisse, Hervé Rivano et Joseph Yu
  • Minimum delay data gathering in radio networks: small interferences do not really matter

15h40 - 16h00

  • Tibor Jordan et Viet Hang Nguyen
  • On universally rigid frameworks on the line

16h00 - 16h50: Pause

16h50 - 18h10

16h50 - 17h10

  • Cyril Gavoille et Pierre Halftermeyer
  • Etiquetage de connexité pour les graphes de genre borné

17h10 - 17h30

  • Pierre Aboulker et Nicolas Bousquet
  • Forbidding cycle with a fixed number of chords

17h30 - 17h50

  • Jorgen Bang-Jensen, Frédéric Havet et A. Karolinna Maia
  • Finding a subdivision of a digraph

17h50 - 18h10

  • Pierre Charbit, Michel Habib et Antoine Mamcarz
  • End vertices of basic graph searches

18h15

  • PC Meeting

20h00 - --h-- Soirée Vins & Fromages

Vendredi 16 Novembre

09h00 - 10h00

09h00 - 09h20

  • Louis Esperet, Laetitia Lemoine, Frédéric Maffray et Grégory Morel
  • Nombre chromatique des graphes sans K4 ni P5 induit

09h20 - 09h40

  • Nicolas Gastineau, Olivier Togni et Hamamache Kheddouci
  • Generalized Packing Chromatic Number

09h40 - 10h00

  • Hervé Hocquard, Mickaël Montassier, André Raspaud et Petru Valicov
  • Coloration forte d'arêtes des graphes subcubiques planaires

10h00 - 11h00 (Exposé Invité)

Pierre Charbit

11h00 - 11h30: Pause

11h30 - 12h50

11h30 - 11h50

  • Eric Angel, Romain Campigotto et Christian Laforest
  • Une nouvelle borne inférieure sur le nombre indépendant d'un graphe

11h50 - 12h10

  • Mamadou M. Kanté, Christian Laforest et Benjamin Momège
  • Un algorithme exact en temps $O^{*}(2^{n})$ vérifiant l'existence d'un chemin entre deux sommets donnés d'un graphe avec transitions interdites.

12h10-12h30

  • F. Delbot, C. Laforest et R. Phan
  • Nouvel algorithme d'approximation pour le vertex cover

12h30 - 12h50

  • Nardjes Menadjelia
  • Le Recouvrement automatique dans une Composition de Services Web Basée Protocole

13h00 - 14h00: Repas