MAZAURIC , Dorian

Un lieu pour comprendre l'informatique et pas juste consommer les produits numériques : c'est un rêve devenu projet, un projet devenu réalité. Voici Terra Numerica. Frédéric Havet et Dorian Mazauric vont nous expliquer en détails la démarche et partager quelques réalisations pour que nous aussi, parents, enseignant·e·s ou tout autre...

Posters expliquant un tour de cartes qui utilise les graphes et le codage binaire

Ce document a pour vocation de présenter, d'expliquer et de jouer avec les graphes et les algorithmes. Ces notions sont centrales en informatique et sont très importantes pour un grand nombre d'applications concernant les réseaux de télécommunication (réseau sans fil, réseau optique, réseau du Web), les réseaux électriques, les réseaux...

We are interesting in this thesis in different networks (optical, wireless, peer-to-peer) each having specificities but sharing some issues: ensure a good quality of service, ensure the stability of the system, minimize ressources and so operating cost. Firstly, we study problem of reconfiguration of the routing in optical networks that...

Posters expliquant le binaire avec un tour de magie

Ce document présente des activités pour découvrir les graphes et les algorithmes de manière simple et ludique. La première partie présente des activités pour découvrir la notion de graphe et montre l'importance que les graphes ont en science. Ensuite, nous abordons la notion d'algorithme. Nous présentons notamment une activité permettant de...

No description

The process number is the number of requests that have to be simultaneously disturbed during a routing reconfiguration phase of a connection oriented network. From a graph theory point of view, it is similar to the pathwidth. However they are not always equal in general graphs. Determining these parameters is in general NP-complete. In this...

The earth mover distance (EMD) or the Mallows distance are example optimal transportation (OT) problems reducing to linear programs. In thiswork, we study a generalization of these problems when the supply and demand nodes are the vertices of two graphs called the supply and the demand graphs. The novel problems embed connectivity constraints...

no abstract

In this paper, we investigate the problem of the representation of simplicial complexes by trees.We introduce and analyze local and global tree representations.We prove that the global tree representation is more efficient in terms of time complexity for searching a given simplex and we show that the local tree representation is more efficient...

Clustering is a fundamental problem in data science, yet, the variety of clustering methods and their sensitivity to parameters make clustering hard. To analyze the stability of a given clustering algorithm while varying its parameters, and to compare clusters yielded by different algorithms, several comparison schemes based on matchings,...

De récentes études montrent que la charge de trafic des routeurs n'a qu'une faible influence sur leur consommation énergétique. Par conséquent, la consommation dans les réseaux est fortement liée au nombre d'équipements du réseau activés (interfaces, chassis, etc). Dans un objectif de minimisation de l'énergie dans les réseaux, il est...

In this paper, we present a distributed algorithm to compute various parameters of a tree such as the process number, the edge search number or the node search number and so the pathwidth. This algorithm requires n steps, an overall computation time of O(n log(n)), and n messages of size log_3(n)+3. We then propose a distributed algorithm to...

We study two characteristics of a small-world graph proposed by Zhang et al. to model complex networks. Our study relies on the recursive structure of the graph. Firstly, we use it to design a labelling scheme in order to create an implicit routing (i.e., a routing scheme based on the label of vertices). Secondly, proving the average distance...

Given a network and a set of source destination pairs (connections), we consider the problem of maximizing the sum of the flow under proportional delay constraints. In this paper, the delay for crossing a link is proportional to the total flow crossing this link. If a connection supports non-zero flow, then the sum of the delays along any path...

In this paper, we address the problem of scheduling the switching of a set of connection requests one after the other from current routing to another pre-determined routing. We propose a model that handles requests using only a constant fraction of the bandwidth of a link, thus generalizing the model proposed in~\cite{CoSe07,JoSo03} for WDM...

It is well known that many NP-hard problems are tractable in the class of bounded pathwidth graphs. In particular, path-decompositions of graphs are an important ingredient of dynamic programming algorithms for solving such problems. Therefore, computing the pathwidth and associated path-decomposition of graphs has both a theoretical and...

In this paper, we address the problem of scheduling the switching of a set of connection requests one after the other from current routing to another pre-determined routing. We propose a model that handles requests using only a constant fraction of the bandwidth of a link, thus generalizing the model proposed in [CoSe07,JoSo03] for WDM...

We study a group-formation game on an undirected complete graph G with all edge-weights in a set W ⊆ R ∪ {−∞}. This work is motivated by a recent information-sharing model for social networks (Kleinberg and Ligett, GEB, 2013). Specifically, we consider partitions of the vertex-set of G into groups. The individual utility of any vertex v is the...

The process number is the minimum number of requests that have to be simultaneously disturbed during a routing reconfiguration phase of a connection oriented network. From a graph theory point of view, it is similar to the node search number, and thus to the pathwidth, however they are not always equal. In general determining these parameters...

It is well known that many NP-hard problems are tractable in the class of bounded pathwidth graphs. In particular, path-decompositions of graphs are an important ingredient of dynamic programming algorithms for solving such problems. Therefore, computing the pathwidth and associated path-decomposition of graphs has both a theoretical and...

Several studies exhibit that the traffic load of the routers only has a small influence on their energy consumption. Hence, the power consumption in networks is strongly related to the number of active network elements, such as interfaces, line cards, base chassis,... The goal thus is to find a routing that minimizes the (weighted) number of...

In this paper, we present a distributed algorithm to compute various parameters of a tree such as the process number, the edge search number or the node search number and so the pathwidth. This algorithm requires n steps, an overall computation time of O(n log(n)), and n messages of size log_3(n)+3. We then propose a distributed algorithm to...

It is well known that many NP-hard problems are tractable in the class of bounded pathwidth graphs. In particular, path-decompositions of graphs are an important ingredient of dynamic programming algorithms for solving such problems. Therefore, computing the pathwidth and associated path-decomposition of graphs has both a theoretical and...