11ème journée d'Optimisation dans les Réseaux le 28/09 à l'IHP

  • Par : Bureau ROADEF
  • 2018-09-17

Le GdT Optimisation des Réseaux du GDR-RO a le plaisir de vous convier à sa 11ème journée d'Automne qui aura lieu dans l'amphi Hermitte à l'Institut Henri Poincaré (IHP) le 28 Septembre 2018.

Le thème principal de cette journée est "Graphes, Algorithmes et Réseaux" avec quatre exposés d'1 heure et

3 exposés de 30 minutes. Pour le moment, il nous reste un créneau de 30 minutes, donc si vous souhaitez intervenir dans cette journée,

n'hésitez pas de nous proposer un exposé en m'envoyant un petit e-mail.

Petite précision : les thèmes des exposés de 30 minutes sont libres et peuvent être différents du thème principal de la journée.

L'adresse de l'IHP est au 11 Rue Pierre et Marie Curie, 75005 Paris

L'inscription est gratuite mais à effectuer en cliquant ici.

Vous trouvez ci-dessous le programme provisoire de la journée.

Merci d'avance pour votre participation.

Bien cordialement,

Viet Hung Nguyen

------------------------------------------------------------------------------------------------------------------------

Le programme provisoire de la journée du Vendredi 28/09/2018:

9h00- 9h30 accueil

9h30-10h30 Michel Habib (IRIF - Université Paris Diderot) Graph searches and geometric convexities in graphs - Joint work with Feodor Dragan and Lalla Mouatadid

Graph convexities or discrete convexities has been studied for a while and has many applications, see for example Farmer and Jamison (1987), Duchet (1988), Chv'atal (2008), Doignon (2017) ....
After an introduction to these notions, we focuse on  the relationships between graph searches and geometric graph convexities. Geometric convexities are of special interest since they are related to antimatroids and therefore to greedy algorithms. Nearly every graph search produces a convex geometry, i.e. every set of visited vertices is convex for some convex geometry. Many convex geometries have been defined on graphs using an interval definition: geodesic, monophonic . . . . We recall that the Lexicographic Breadth First Search (LexBFS) captures these convex geometries on many graph classes and we finish with some new properties on AT-free graphs.
We hope to  convince that convex geometries are the good framework to understand the greedy properties of graph searches, such as BFS, DFDS, LexBFS and LexDFS.

10h30 - 11h00 Pause café

11h00 - 12h00 Yannis Manoussakis (LRI - Université Paris Sud) Subgraphs with specified color properties in vertex- or edge-colored graphs

In general, graphs are divided in two important classes,  directed and undirected ones. However, because of recent technological developments, these two classes of graphs are not powerful enough to model all existing real-life constraints. For example, if one wants to differentiate highways from national roads, and main from secondary roads, a good idea would be to use colors. As another example, the Web graph may be considered as a vertex-colored graph where the color of a vertex represents the content of the corresponding page (red for mathematics, yellow for physics, etc.). When the edges/vertices of graphs are colored, then we talk about c-edge/vertex colored graphs (c is the number of colors), models which in fact generalize various  classes of graphs. In general, one can observe that problems related to colored graphs often consist in finding subgraphs such as paths, cycles and trees, with, in addition, specified constraints on colors.

 

In the case of c-edge-colored graphs, one such natural constraint is the proper coloring one, i.e., any two adjacent edges differ on colors.  Given such an edge-colored graph, original problems correspond to extracting  subgraphs,   for example, Hamiltonian and Eulerian paths or cycles, trees, etc., colored in this specified pattern.  Although a large body of work has already been done, in the most of these researches the number of colors is restricted to two. For instance, while it is well known how to find efficiency a properly edge colored Hamiltonian cycle in a 2-edge colored complete graph, it is a long-standing question how to find such cycles in complete graphs whose edges are colored by any number of colors.  Here we survey a series of results concerning proper subgraphs in c-colored graphs, for arbitrarily c.

 

In the case of vertex-colored graphs, we deal with  tropical subgraphs, a concept   with direct applications to the web graph and in bioinformatics (Multiple Sequence Alignment Pipeline  or for multiple protein-protein Interaction networks). More precisely, given a vertex-colored graph, a tropical subgraph (induced or otherwise) is defined to be a subgraph where each color of the initial graph appears at least once. Notice that in a tropical subgraph, adjacent vertices can receive the same color, thus a tropical subgraph may not be properly colored. Potentially, many graph invariants, such as the domination number, the vertex cover number, maximum matchings, independent sets, connected components, shortest paths, etc. can be studied in their tropical version. This notion is close to, but somewhat different from the colorful concept (all colors of the subgraph are different) used for paths and elsewhere in vertex-colored graphs. It is also related to the concepts of color patterns (the subgraph has fixed color patterns) used in bio-informatics.  Here we explain some results on our ongoing work on tropical dominating sets, vertex covers, connected subgraphs, maximum matchings and tropical homomorphisms.

 

12h00 - 12h30  Admed Mabrouk (Engie) Proposition d’un système d'aide au suivi de l'état de santé des éoliennes : une approche à base de réseaux bayésiens

12h30-13h30 buffet déjeuner offert

13h30-14h30 Yann Vaxes (LIS- Université Aix-Marseille) Au coeur des réseaux hyperboliques

In the first part of the talk, we will introduce Gromov hyperbolicity and recall several characterizations of delta-hyperbolic geodesic metric spaces and graphs.

In the second part, we investigate the impact the negative curvature has on the traffic congestion in large-scale networks. We prove that every Gromov hyperbolic network G admits a core, 

thus answering in the positive a conjecture by Jonckheere, Lou, Bonahon, and Baryshnikov, Internet Mathematics, 7 (2011) which is based on the experimental observation by 

Narayan and Saniee, Physical Review E, 84 (2011)  that real-world networks with small hyperbolicity have a core congestion. Namely, we prove that for every subset X of n 

vertices of a graph G with delta-thin geodesic triangles there exists a vertex m of G such that the ball B(m,4delta)  of radius 4delta centered at m intercepts at least one half of the 

total flow between all pairs of vertices of X, where the flow between two vertices x,y of  X is carried by geodesic (or quasi-geodesic) (x,y)-paths.  We show that the point 

m can be constructed in the following way: take a median point m* of X (a point minimizing the sum of distances to the points of X) in the injective hull of G and then a closest to m* point in G.

In the third part of the talk, (and if the time will permit), we will describe a simple factor 8 approximation algorithm for optimal hyperbolicity of an n-vertex graph in optimal O(n^2) time (assuming that the input is the distance matrix of the graph). 

 

The talk is based on the papers 

[1] V. Chepoi, F. Dragan, and Y. Vaxès, Core congestion is inherent in hyperbolic networks, SODA 2017, <http://arxiv.org/abs/1605.03059> .

[2] J. Chalopin, V. Chepoi, F. Dragan, G. Ducoffe, A. Mohammed, and Y. Vaxès, Fast approximation and exact computation of negative curvature parameters of graphs, SoCG 2018, <https://arxiv.org/abs/1803.06324>.

14h30-15h30  : Mourad Baiou (LIMOS - Université de Clermont Auvergne) Sparsest Cut via Max Cut

15h30-16h00 pause café

16h00-16h30 Dimitri Watel (Samovar -ENSIIE)  Maximum Residual Flow Problem with Arc Destruction

The maximum Residual Flow Problem with Arc Destruction is posed as follows. Given a directed network G, find a maximum flow such that when k arcs are deleted from G the value of a maximum flow in the residual network is maximum. It is proved that the problem is polynomial time solvable for k = 1 whereas it shown to be NP-hard for k = 2. The Adaptative Maximum Flow Problem was first adressed as an alternative to the robust maximum flow problem. In this model, the flow can be adjusted after the arc failures occurred. In this presentation, we are concerned with the Adaptative Maximum Residual Flow Problem, that is the maximum Residual Flow Problem with Arc Destruction when the flow can be reoriented. We focus on three variants of the problem : the original problem in which the attacker may destroy a given number k of arcs ; a variant where some of the arcs cannot be destroyed ; and a last variant where each destruction is associated to a given cost and where the attacker has a given destruction budget. For each of the three problems, we focus on complexity results. Those results depend on the maximum number of destructible arcs that can be found on a single path from the source to the sink. It has been proven that all the three problems are NP-Complete when this parameter is greater or equal to 4. We complete the results when we restrict the problem to instances where this parameter equals 2 or 3.

 

16h30-17h00 Intervenant et titre à préciser



------------------------------

--------------------------------------------
Viet Hung Nguyen Associate Professor  LIP6