Actualités du LIPN

[LIPN] [CNRS] [Université Paris 13]

To content | To menu | To search

Keyword - graphes

Entries feed - Click here to abridge

Past posts

Monday 18 June 2012

[Journées BigData] Appel à soumission, Big Data Mining and Visualization (Fouille et Visualisation de Données Massives), 18 et 19 juin à Tours

fr 

Monday 18 June 2012 at 09.00 AM — Conferences

Appel à communication

Journées communes aux Groupes de Travail EGC et AFIHM


Fouille et Visualisation de Données Massives

Big Data Mining and Visualization

 

Le lundi  18 et  le mardi  19 juin 2012 à Tours

______________________________
Dates importantes
______________________________

Le  18 mai : soumission du résumé de 10 lignes

L’inscription est gratuite mais obligatoire avant le 04 juin 2012.

______________________________

Comment participer et s’inscrire

______________________________
_

Si vous êtes intéressé par faire une présentation nous vous prions de manifester votre intention en soumettant via easychair un résumé de 10 lignes au plus tard le 18 mai 2012. Les présentations pourront durer 30 min et concerner : vos travaux récents, une présentation de synthèse de votre équipe, les résultats d’une thèse en cours, des données sur lesquelles vous travaillez, des présentations de projets en cours, etc. Un intérêt particulier est porté aux travaux menés par les doctorants.

L’inscription est gratuite mais obligatoire avant le 04 juin 2012. Pour vous inscrire cela se passe ici. 


________________
Objectifs :
________________

Les groupes de travail de l’association EGC : "Fouille de Données Complexes" (GT-FDC), "Fouille de Grands Graphes" (GT-FGG) et "Visualisation d’informations, interaction et fouille de données" (GT-VIF, commun avec l’AFIHM) organisent conjointement deux journées thématiques visant d’une part à poursuivre les activités des groupes et d’autre part à développer des axes communs autour de la complexité liée à la fouille des données massives (big data). Dans ce contexte, les problématiques abordées lors de ces deux journées peuvent concerner les processus (acquisition, structuration, extraction d’information et de connaissances et la visualisation) ou les données elles-mêmes. L’objectif de ces journées est de rassembler l’ensemble des acteurs de la communauté scientifique intéressés par ces nouvelles approches de la fouille de données massives afin de susciter des interactions entre chercheurs du domaine et d’animer/de dynamiser cette communauté. Des conférenciers invités présenteront leurs travaux.

De façon non limitative, nous sollicitons des communications sur les thématiques suivantes :

 

  • Connaissances et classification d’objets complexes multi-sources
  • Structuration et organisation des données massives (big data)
  • Solutions émergentes en matière de traitements parallèles, décentralisés et/ou collaboratifs des données (cloud computing, GPU, ...)
  • Visualisation d’informations, fouille visuelle de données, visualisation analytique
  • Classification interactive, fouille et découverte interactive supervisée ou non supervisée,
  • Fouille et analyse des données de grands graphes
  • Dynamique des grands graphes
  • Architectures logicielles et matérielles pour la fouille et la visualisation de données massives
  • Applications et réalisations industrielles : données médicales et scientifiques, marketing, réseaux sociaux, ...
_______________________________

subventions pour participation  

_______________________________     

Des subventions seront accordées dans différentes conditions (voir procédure sur le site de l’organisation locale) :

  • le transport des orateurs étudiants pourra être pris en charge, sur la base des titres de transports de train 2ème classe,
  • pour les membres de l’AFIHM (Association Francophone d’Interface Homme-Machine), les déplacements peuvent être pris en charge.
Concernant votre venue à Tours, nous vous encourageons à consulter les informations d’hébergement sur la ville ainsi que la localisation de ces journées.

______________________________
Comité d’organisation
______________________________

GT - FDC (http://eric.univ-lyon2.fr/~gt-fdc/)
Guillaume Cleuziou (LIFO, Univ. Orléans)
Cyril de Runz (CReSTIC, Univ. de Reims)
Mustapha Lebbah (LIPN, Univ. Paris 13)
Cedric Wemmert (LSIIT, Univ. Strasbourg)

GT - FGG (http://www.polytech.univ-nantes.fr/GT-FGG/)
Hanene Azzag (LIPN, Univ. Paris 13)
Lydia Boudjeloud (LITA, Univ. Metz)
Rushed Kanawati (LIPN, Univ. Paris 13)
Fabien Picarougne (LINA, Univ. Nantes)
Bruno Pinaud (LABRI, Univ. Bordeaux)

GT - VIF (http://wiki.afihm.org/index.php?title=GT_VIF)
Monique Noirhomme (FUNDP, Namur, Belgique)
Pascale Kuntz (LINA, Univ. Nantes)
David Auber (LABRI, Univ.  Bordeaux)
Gilles Venturini (LI, Univ. Tours)

Organisateurs locaux :    Octavio Razafindramanana, Barthélémy Serres, Gilles Venturini

Tuesday 22 March 2011

Détermination des éléments les plus vitaux pour des problèmes de graphes

fr 

Tuesday 22 March 2011 at 12.00 PM — Seminars

Le séminaire AOC recevra le 22 mars (à 12h exceptionnellement) Sonia Toubaline (Dauphine).

Nous considérons les versions des k arêtes (sommets) les plus vitales (vitaux) et de min arête (sommet)-bloqueur pour différents problèmes de graphes. Etant donné un problème d’optimisation P défini sur un graphe valué, le problème "k Most Vital Edges (Nodes) P" consiste à déterminer un sous-ensemble de k arêtes (sommets) dont la suppression du graphe dégrade au maximum la valeur optimale de P. Le problème complémentaire, "Min Edge (Node) Blocker P", consiste à supprimer un sous-ensemble d’arêtes (sommets) de cardinalité minimale tel que la valeur optimale de P est, selon la nature de P, inférieure ou égale ou supérieure ou égale à un seuil spécifique. Nous étudions la complexité, l’approximation et la résolution exacte de ces quatre versions pour les problèmes de graphes suivants : arbre couvrant de valeur minimale, affectation de valeur minimale, stable de valeur maximale, couverture de valeur minimale, 1-médian, 1-centre, flot de coût minimal et flot maximum. Ainsi, nous proposons des preuves de NP-difficulté au sens fort ou de polynomialité pour des classes particulières de graphes, des résultats d’approximation, des algorithmes d’énumération explicite ou implicite pour résoudre ces problèmes ou encore une formulation par programmation linéaire.

Tuesday 6 April 2010

Minorité stochastique et de ses particularités

fr 

Tuesday 6 April 2010 at 01.00 PM — Seminars

Le séminaire OCAD recevra le 6 avril Damien Regnault (ATER au LIF-CMI, Marseille).

Cet exposé commence par la présentation rapide de la règle Minorité stochastique et de ses particularités. Ensuite, je présenterai une application de cette règle pour modéliser la formation de quasi-cristaux.

Considérons un graphe où chaque sommet reçoit la couleur noire ou blanche. Une arête contient une erreur si elle relie deux sommets de la même couleur. Minorité est une dynamique stochastique minimisant rapidement l’énergie. Sous cette dynamique, un sommet, chosi aléatoirement et uniformément parmi l’ensemble des sommets, peut changer d’état si au moins la moitié des arêtes qui lui sont adjacentes sont erronées.. Cette dynamique est sensible à la topologie du graphe et son analyse fine s’est révélée compliquée.

En physique, dans les années 70, il était conjecturé que toutes les structures ordonnées soient périodiques. En 1984, un contre-matériaux fût découvert et reçu le nom de quasi-cristal. Dès 1974, Penrose avait présenté un structure théorique ordonnée et apériodique. Le but de notre projet est de présenter un modèle pour expliquer la formation d’une telle structure. Pour cela, nous considérons le modèle des pavages par coupe et projection (qui contient le pavage de Penrose). En définissant une notion d’erreur et d’énergie sur ces pavages, la règle Minorité procédant par flips permet de converger rapidement expérimentalement vers une structure ordonnée qui selon la famille de pavages par coupe et projection considérée est soit périodique, soit apériodique. Je présenterai nos résultats expérimentaux ainsi que notre analyse de cette dynamique pour les pavages 2 vers 1 (mots sur deux lettres).

Tuesday 1 December 2009

Soutenance d'habilitation de Mario Valencia-Pabon

fr 

Tuesday 1 December 2009 at 02.00 PM — PhD & Habilitations defends

Mario Valencia-Pabon soutient son HDR le 1er décembre 2009 à 14h intitulée « Variations du problème la coloration des graphes : aspects théoriques et algorithmes ».

Le jury est composé de

  • Cristina Bazgan (LAMSADE, Paris-Dauphine)
  • Victor Chepoi (LIF, Marseille)
  • Dominique de Werra (EPFL, Suisse)
  • Gérard Duchamp (LIPN, Paris-Nord)
  • Sylvain Gravier (IJF, Grenoble)
  • Mekkia Kouider (LRI, Paris-Sud)
  • Christian Lavault (LIPN, Paris-Nord)
  • Gérard Plateau (LIPN, Paris-Nord)

Cette étude porte sur de nouvelles propriétés pour l’obtention des algorithmes polynomiaux et sur l’analyse de la complexité algorithmique de certaines variantes du problème de la coloration dans certaines familles des graphes.

L’étude comporte trois parties :

  • La b-coloration des sommets d’un graphe : problème APX-complet dans le cas général, mais polynomial pour les graphes P4-sparse;
  • Problèmes de coloration dans le produit direct de certains graphes sommet-transitifs;
  • Le problème de la somme-coloration dans certaines familles de graphes : P4-sparse, multicycles et bloc.

Tuesday 9 December 2008

On variations of the graph coloring problem

fr 

Tuesday 9 December 2008 at 12.30 PM — Seminars

Le séminaire OCAD accueille Flavia Bonomo (université de Buenos Aires, Argentine).

A coloring of a graph is an assignment of natural numbers to its vertices in such a way that adjacent vertices receive different colors. This well-known problem is a basic model for frequency assignment and resource allocation problems. In order to take into account particular constraints arising in practical settings, more elaborate models of vertex coloring have been defined in the literature. One of such generalized models is the list-coloring problem, which considers a prespecified set of available colors for each vertex. The list-coloring problem is NP-complete even for split graphs, interval graphs, and bipartite graphs.

We consider some particular cases of the list-coloring problem: μ-coloring, where each vertex has its own upper bound for the color to be assigned, and (γ,μ)-coloring, where each vertex has its own lower and upper bounds for the color to be assigned. The μ-coloring problem arises in the context of classroom allocation to courses, where each course must be assigned a classroom which is large enough so it fits the students taking the course. We will present some polynomial time algorithms to solve these problems on classes where list-coloring is NP-complete.

Thursday 27 November 2008

Soutenance d'habilitation de Vlady Ravelomanana

fr 

Thursday 27 November 2008 at 02.00 PM — PhD & Habilitations defends

Vlady Ravelomanana soutient son HDR le 27 novembre 2008 à 14h intitulée « Graphes aléatoires, optimisation, algorithmique distribuée : approches analytiques ».

Le jury est composé de

  • Nadia Creignou (LIF -- Marseille),
  • Luc Devroye (McGill),
  • Gérard Duchamp (LIPN-P13),
  • Philippe Flajolet (INRIA),
  • Christian Lavault (LIPN-P13),
  • Rémi Monasson (LPT -- ENS),
  • Hsien-Kuei Hwang (Academia Sinica, Taipei),
  • Brigitte Vallée (GREYC - Caen).

Nous présentons un ensemble de résultats portant sur trois axes distincts, tous obtenus en utilisant des approches analytiques. Dans ces travaux, nous faisons intervenir des méthodes de combinatoire analytique et d’algorithmique. Ces outils sont utilisés pour répondre aux problèmes suivants :

  1. l’étude des composantes géantes des graphes et hypergraphes aléatoires,
  2. la transition de phase de 2–XORSAT, l’analyse en moyenne d’un algorithme exact d’optimisation, et
  3. l’élection et l’initialisation dans des réseaux radio.