Jeudi 25 novembre 2010 de 13h30 à 18h00 à l’ENS de Lyon
Vendredi 26 novembre de 9h00 à 16h00 à l’INSA de Lyon
Dans le cadre du pôle ResCom du GDR ASR , des journées non thématiques sont organisées deux fois par an. Elles portent sur l’ensemble des thèmes du pôle ResCom :
- Réseaux (architecture, protocoles, performances),
- Algorithmique
- Théorie des Graphes appliquée aux Réseaux.
Cette édition des journées ResCom aura lieu à Lyon, le jeudi après-midi sur le site de l’ENS de Lyon et le vendredi sur le site de l’INSA.
Ces journées s’adressent à tous les acteurs (doctorants, chercheurs juniors, chercheurs seniors ; industriels et académiques) de la communauté ResCom. Le but est de permettre à tous de présenter à la communauté vos derniers résultats, susciter des échanges et des interactions.
Vous pouvez dès à présent réserver ces dates sur votre agenda.
Les propositions de communication (prévoir des exposés de 20′) comportant :
- Le titre de l’exposé
- le nom de l’orateur (et des éventuels co-auteurs)
- son organisme d’affiliation
- un titre / résumé (pour organiser les sessions)
sont à envoyer avant le 28 octobre 2010 à :
fabrice.valois chez insa-lyon.fr ET christophe.crespelle chez ens-lyon.fr
Nous attendons aussi bien des exposés de travaux en cours, que la présentation de résultats clefs ou la proposition d’exposés longs.
L’inscription aux journées est gratuite mais obligatoire pour des raisons d’organisation (envoyer un mail aux organisateurs).
Le programme et les détails d’organisation seront postés sur cette page.
En espérant vous voir nombreux lors de ces journées.
Organisateurs:
- Christophe Crespelle
- Fabrice Valois
Dates clefs:
- Date limite d’annonce d’exposé : 28 octobre 2010
- Journées : 25 & 26 Novembre 2010
Lieu:
Les journées commencent, le jeudi après-midi, dans la salle des thèses de l’ENS Sciences, site Monod.
Programme:
Exposés invités:
Stéphan Thomassé, LIRMM, Université de Montpellier 2
Jeudi 25 novembre à 13h30, salle des thèses de l’ENS Sciences, site Monod
Multicut and Multiflow in FPT time
The study of cuts and flows is one of the most active field in combinatorial optimization. However, if the simplest case, involving one source and one sink, is algorithmically tractable, the problem becomes hard as soon as one deal with multiple terminals. For instance, given two requests x1,y1 and x2,y2 in a directed graph, it is NP-complete to decide if there exists two disjoint directed paths, respectively from x1 to y1 and from x2 to y2.
The picture changes dramatically when considering undirected graphs, in which case the celebrated result of Robertson and Seymour asserts that given k requests x1,y1,x2,y2,…,xk,yk, one can decide in cubic time if there exists k disjoint paths connecting all pairs xi,yi. The catch is of course that cubic time refers to the instance size $n$. From their work, the complexity of the k-path problem is O(f(k)n^3), where the function f is by no mean polynomial, since the question is NP-complete when k is part of the input.
This result received considerable attention, both since this is the key-tool for computing a given minor in a graph, but also because it has opened a breach in the classical NP-complete/P duality. Indeed, the difficulty of the k-path problem does not depend on the size of the instance, but rather on the number of paths we are looking for. In other words, the parameter containing the hardness of the problem is the number k of paths. In a more general way, a problem is fixed parameter tractable (FPT) with respect to parameter k (e.g. solution size, treewidth, …) if, for any instance of size n, it can be solved in time O(f(k)n^c) for some fixed c.
The dual problem of finding disjoint paths from a source s to a sink t is the cut problem where one asks for a set of edges which deletion separates s from t. Menger theorem, or more generally LP-duality, asserts that the maximum number of disjoint st-paths is equal to the minimum size of a cut. This property no more holds when considering multiple requests, where the maximum number of disjoint paths connecting requests is only an obvious lower bound for the size of a multicut, i.e. a set of edges which deletion separates xi from yi for every request x_i,y_i in R. Formally, we study the following problem:
MULTICUT
Input: A graph G, a set of requests R, an integer k.
Parameter: k
Output: TRUE if there is a multicut of size at most k, otherwise FALSE.
The status of this problem is one of the main open problems in fixed parameter complexity.
We recently provided with Nicolas Bousquet and Jean Daligault an FPT algorithm for MULTICUT. An independent FPT algorithm was found by Marx and Razgon using a randomized approach.
Jean-Jacques Pansiot, LSIIT, Université de Starsbourg
Vendredi 26 novembre à 9h
Sur les traces d’Internet
Obtenir une carte de tout ou partie du réseau Internet intéresse aussi bien les concepteurs de protocoles réseau qui veulent des modèles réalistes pour évaluer leurs propositions, que les spécialistes de graphes de terrain qui y voient un exemple de réseau dynamique. En apparence ce réseau devrait être facile à cartographier puisque construit par l’homme et constitué d’équipements informatiques.
En réalité le problème est complexe du fait de la construction distribuée et hétérogène du réseau. A défaut d’obtenir ces cartes des opérateurs, toujours discrets sur la topologie de leur réseau, il faut se résoudre à les construire par des mesures. Depuis une quinzaine d’années et jusqu’à une date récente, tous les outils pour le faire étaient basés sur le principe de la commande traceroute qui utilise des messages du protocole ICMP. Même si les résultats obtenus sont intéressants, plusieurs problèmes sont à résoudre : supprimer les artefacts dûs à traceroute, obtenir une bonne exhaustivité en termes de noeuds et d’arêtes du graphe, à moindre coût, et finalement passer d’un graphe d’adresses IP (fourni par traceroute) à un graphe d’équipements (routeurs) qui est la représentation souvent la plus pertinente (problème d’aliasage). Des solutions partielles ont été proposées pour ces différents problèmes, et sont encore l’objet d’améliorations.
Nous proposons ici une approche différente basée sur des messages IGMP (ceux de l’outil mrinfo) permettant d’interroger des routeurs multicast et d’obtenir leur voisinage en une seule opération. Appliquée récursivement cette approche permet d’obtenir rapidement un sous-graphe exhaustif de routeurs multicast interconnectés, sans problème d’alias ni d’artefact. De plus cette approche permet aussi de détecter des équipements (switchs) de niveau 2 ce qui enrichit la topologie en un graphe de routeurs et de switchs. Nous présentons quelques résultats sur la présence de ces switchs, leurs interconnexions avec les routeurs, et l’impact qu’ils ont sur la distribution des degrés des routeurs telle que vue par traceroute.
Finalement cette approche ne peut pas se généraliser telle quelle à Internet tout entier, certains routeurs
n’activant pas le multicast, ou les messages IGMP, et d’autres équipements filtrant ces messages en transit. Nous présentons donc les premières ébauches d’un outil distribué, Merlin, permettant de s’affranchir au moins partiellement de ces limitations.
Participants:
Merci de vous inscrire en nous retournant le bulletin suivant par mail.
=------= Bulletin d'inscription à renvoyer =------= Nom : Prénom : Mail : Affiliation : Participera à la demi-journée du 25 novembre : oui Non Participera à la journée du 26 novembre : oui Non =------= Bulletin d'inscription à renvoyer =------=
ABDEDDAIM Nazim LIG, Univ. Grenoble ACHIR Nadjib L2TI, Univ. Paris 13 AIT SAADI Nadjib HIPERCOM, INRIA Rocquencourt ALLAL Salim L2TI, Univ. Paris 13 ALLALI Oussama LIP6, Univ. Paris 6 AMADOU Ibrahim SWING / CITI, INSA Lyon ANDRIYANOVA Iryna ETIS, Univ. Cergy-Pontoise AUGE-BLUM Isabelle SWING / CITI, INSA Lyon BANAOUAS Iskander HIPERCOM, INRIA Rocquencourt BEAUDAUX Julien LSIIT, Univ. Strasbourg BEGIN Thomas RESO / LIP, ENS Lyon BELLABAS Alia IRISA, Univ. Rennes BEN SAAD Leila LIP / CITI, Univ. Lyon BEREZIN Maria Eugenia LIG, Univ. Grenoble BILDEA Ana LIG, Univ. Grenoble BORGNAT Pierre Labo Physique, ENS Lyon BOUSSETTA Khaled L2TI, Univ. Paris 13 CATUSSE Nicolas LIF, Univ. Marseille CHAUVENET Cedric CITI, INSA Lyon COUDERT David MASCOTTE, Sophia COURBON Michel Univ. St Etienne CRESPELLE Christophe D-NET / LIP, ENS Lyon DARTIES Benoît LE2I, Univ. Bourgogne DIOURI Mehdi RESO / LIP, ENS Lyon DOMGA KOM GUEM Rodrigue LIP / CITI, INSA Lyon DUCOURTHIAL Bertrand UTC, Univ. Compiègne DUCROCQ Tony POPS / LIFL, Univ. Lille ERDELJ Milan LIFL, Univ. Lille FARSI Abdelhak L2TI, Univ. Paris 13 FLEURY Eric D-NET / LIP, ENS Lyon FOURTY Nicolas SWING / CITI, INSA Lyon FRIGGERI Adrien D-NET / LIP, ENS Lyon FRIKHA Ahmed IRISA, Univ. Rennes GALLAIS Antoine LSIIT, Univ. Strasbourg GENON-CATALOT Denis SWING / CITI, INSA Lyon GODFROY Quentin LaBRI, Univ. Bordeaux GOUVY Nicolas POPS / LIFL, Univ. Lille HADDAD Mohammed LIESP, Univ. Lyon 1 ILCINKAS David LaBRI, Univ. Bordeaux KHALIFE Hicham COMET / LaBRI, Univ. Bordeaux KRICHEN Mariem PRiSM, Univ. Versailles LABOUREL Arnaud LIF, Univ. Marseille LAMPIN Quentin Orange Labs & CITI, INSA Lyon LANCIN Aurélien MASCOTTE, Sophia LEMMOUCHI Slimane LIESP, Univ. Lyon 1 MAGNIEN Clémence LIP6, Univ. Paris 6 MOLLE-CAILLOUET Christelle RWTH Aachen, Germany MOURADIAN Alexandre SWING / CITI, INSA Lyon NEPOMUCENO Napoleao MASCOTTE, Sophia OPRESCU Iuniana LAAS-Orange, Univ. Toulouse ORGERIE Anne-Cécile LIP, ENS Lyon OUEDRAOGO Frédéric Univ. Koudougou, Burkina Faso OUNI Anis SWING / CITI, INSA Lyon PANSIOT Jean-Jacques LSIIT, Univ. Strasbourg PAVKOVIC Bogdan LIG, Univ. Grenoble RADAK Jovan POPS / LIFL, Univ. Lille REUTER Emmanuel INRETS, Lyon RIVANO Hervé CITI, INSA Lyon ROMDHANI Bilel CITI, INSA Lyon ROTH Damien LSIIT, Univ. Strasbourg ROUSSEAU Franck LIG, Univ. Grenoble RUNSER Katia SWING / CITI, INSA Lyon SALAH BRAHIM Abdelhamid LIP6, Univ. Paris 6 TABIA Nourredine SET-UTMB, Univ. Belfort-Montbeliard TAHIRI Issam MASCOTTE, Sophia TEIXEIRA DE OLIVEIRA Carina LIG, Univ. Grenoble THEOLEYRE Fabrice LSIIT, Univ. Strasbourg THIERRY Eric LIP, ENS Lyon THOMASSÉ Stéphan LIRMM, Univ. Montpellier 2 TOURANCHEAU Bernard CITI, INSA Lyon VALOIS Fabrice CITI, INSA Lyon VERGARA GALLEGO Maria Isabel LIG, Univ. Grenoble WANG Qinna D-NET / LIP, ENS Lyon YANG Fei CITI, INSA Lyon
Infos pratiques:
Lieux
Le 25 : ENS de Lyon, Site Monod, salle des thèses
Accès : Metro B, direction Stade de Gerland, arrêt Debourg
Plan
Le 26 : INSA Lyon, Bâtiment C. Chappe, Amphi.
Accès : Tramway T1, direction IUT Fesyssine, arrêt Gaston Berger.
Plan
