Academic literature on the topic 'Graphes de propriétés'

Les grands réseaux de communication sont partout, des centres de données avec des millions de serveurs jusqu’aux réseaux sociaux avec plusieurs milliards d’utilisateurs.Cette thèse est dédiée à l’étude fine de la complexité de différents problèmes combinatoires sur ces réseaux. Dans la première partie, nous nous intéressons aux propriétés des plongements des réseaux de communication dans les arbres. Ces propriétés aident à mieux comprendre divers aspects du trafic dans les réseaux (tels que la congestion). Plus précisément, nous étudions la complexité du calcul de l’hyperbolicité au sens de Gromov et de paramètres des décompositions arborescentes dans les graphes. Ces paramètres incluent la longueur arborescente (treelength) et l’épaisseur arborescente (treebreadth). Au passage, nous démontrons de nouvelles bornes sur ces paramètres dans de nombreuses classes de graphes, certaines d’entre elles ayant été utilisées dans la conception de réseaux d’interconnexion des centres de données. Le résultat principal dans cette partie est une relation entre longueur et largeur arborescentes (treewidth), qui est un autre paramètre très étudié des graphes. De ce résultat, nous obtenons une vision unifiée de la ressemblance des graphes avec un arbre, ainsi que différentes applications algorithmiques. Nous utilisons dans cette partie divers outils de la théorie des graphes et des techniques récentes de la théorie de la complexité<br>Large scale communication networks are everywhere, ranging from data centers withmillions of servers to social networks with billions of users. This thesis is devoted tothe fine-grained complexity analysis of combinatorial problems on these networks.In the first part, we focus on the embeddability of communication networks totree topologies. This property has been shown to be crucial in the understandingof some aspects of network traffic (such as congestion). More precisely, we studythe computational complexity of Gromov hyperbolicity and of tree decompositionparameters in graphs – including treelength and treebreadth. On the way, we givenew bounds on these parameters in several graph classes of interest, some of thembeing used in the design of data center interconnection networks. The main resultin this part is a relationship between treelength and treewidth: another well-studiedgraph parameter, that gives a unifying view of treelikeness in graphs and has algorithmicapplications. This part borrows from graph theory and recent techniques incomplexity theory. The second part of the thesis is on the modeling of two privacy concerns with social networking services. We aim at analysing information flows in these networks,represented as dynamical processes on graphs. First, a coloring game on graphs isstudied as a solution concept for the dynamic of online communities. We give afine-grained complexity analysis for computing Nash and strong Nash equilibria inthis game, thereby answering open questions from the literature. On the way, wepropose new directions in algorithmic game theory and parallel complexity, usingcoloring games as a case example

Les problèmes de décomposition de graphes sont au coeur de la théorie des graphes. Dans cette thèse nous étudions le problème Graphe_Partition qui, étant donné un graphe d'ordre n et une partition de n (séquence d'entiers positifs dont la somme est égale à n), consiste à déterminer s'il existe une partition des sommets du graphe telle que chaque ensemble de cette partition induit un sous-graphe connexe et la séquence des ordres de ces sous-graphes est une permutation de la partition de n. Si une telle partition des sommets existe, nous dirons que le graphe est décomposable pour cette partition de n. Un graphe arbitrairement décomposable est un graphe décomposable pour toutes les partitions de n. Le problème_Partition a déjà été l'objet de plusieurs études. Il a notamment été montré que celui-ci est NP-complet même restreint à la classe des arbres et que les arbres arbitrairement décomposables sont principalement de degré inférieur ou égale à 3. Dans cette thèsenous avons dans un premier temps approfondie l'étude structurelle des arbres arbitrairement décomposables et commencé l'étude structurelle des graphes décomposables. Nous avons pu montrer que les graphes décomposables de longueur arbitrairement grande étaient exactement l'ensemble des peignes. Nous avons donné une construction par récurrence qui permet de construire des peignes arbitrairement décomposables contenant un nombre de sommets de degré 3 et de longueurs arbitrairement grands. Nous avons apporté également une première contribution concernant l'étude structurelle des graphes arbitrairement décomposables minimaux (quelle que soit l'arrête que l'on retire, le graphe restant n'est plus décomposable). Puis dans un deuxième temps, nous nous sommes intéressés à l'aspect algorithmique. Nous avons notamment montré que pour des partitions de n contenant peu d'entiers, il était possible de déterminer assez rapidement si un graphe était décomposable pour cette partition. Nous avons étendu ce résultat aux graphes contenant un petit nombre de sommets de degré 3. Enfin, nous avons montré qu'il était possible de déterminer assez rapidement si un arbre de large diamètre est arbitrairement décomposable<br>Graphes decomposition problems are in the heart of graphes theory. In this thesis we study the problem Graph_Partition wich in defined as follow. Being done a n-vertex graph ans a partition of n (a sequence of positives integers whose sum is equal to n), does it exists a partition of the vertex set such that every set of the partition induce a connected sub-graph, and the sequence of vertices numbers of these sub-graphes is a permutation of the partition of n. If a such partition of the vertex set exists, we say that the graph is decomposable for this partition of n. The problem Graph_Partition has already been the target of several studies. It has been shown that this problem is NP-Complet even restreint to the set of trees, and arbitrarily decomposable trees are principaly of degree 3. In this thesis we have in a first time continued structural study on arbitrarily decomposable and we have started structural studies on arbitrarily decomposable graphs. We have shown that arbitrarily decomposable trees with length arbitrarily haigh are exactly the set of combs. We gave an introduction building wich allow to construct arbitrarily decomposable combs with a number of degree 3 vertices and a length arbitrarily high. We have also given a first contribution concerning structural study of arbitrarily decomposable minimal graphs (whatever the edge you remove from the graph, the remaining graph is not arbitrarily decomposable). In a second time we study algorithmic aspect. We have shown that if we consider partition of n containing few integers, it is possible to determine enough quickly if a graph in decomposable for this partition of n. We have extended this result over the graphs containing few degree 3 vertices. Finally we have shown that it is possible to decide enough quickly if a tree with large diameter in arbitrarily decomposable

Dans cette these on s'interesse a la propriete (t) pour les groupes discrets et aux spectres des operateurs associes aux marches aleatoires sur ces groupes. On etudie aussi le rayon spectral de ces operateurs sur certains graphes

Les réseaux de Petri (RdP) sont un formalisme puissant de modélisation et d'évaluation des systèmes dynamiques complexes. Une classe particulière des RdP, que sont les graphes d'événements valués (GdEV) fortement connexes, permet plus particulièrement d'analyser les systèmes cycliques sans conflit structurel. Lorsque la notion de flux apparaît (système fluide, structure à haut débit, etc. ) il est possible d'utiliser un modèle GdEV continu (GdEVC). Le plus souvent, les méthodes d'analyse des propriétés temporelles des RdP continus se basent sur le développement du graphe d'évolution qui représente la dynamique du système. . .

This work is dedicated to the study of infinite structures (or graphs) which admit a finite presentation. To the equivalences between those presentations and to the geometrical and decidability properties concerning them. The study starts with stack based structures,mainly the prefix recognizable ones. We establish various presentations for those structures, as solutions of equational systems,by transformation of the infinite complete binary tree and by word rewriting. We then study the term-automatic structures and give them,in particular, a new characterization by mean of equational systems. We finally study the families of graphs defined by ground term rewriting. We introduce a new family of graphs of this kind defined as solutions of equational systems. We then study the logics decidable over those graphs and establish some of their geometrical properties.

La largeur d'arborescence est une notion intéressante d'un point de vue théorique mais également algorithmique puisque beaucoup de problèmes NP-difficiles deviennent polynomiaux quand on se restreint aux graphes de largeur d'arborescence bornée. Elle est étroitement liée à la notion de q-clique-mineur qui lui est duale et à une propriété des familles de graphes dite propriété d'Erdos-Posa. De plus, le caractère borné de la largeur d'arborescence est lié à l'interdiction de graphes planaires en tant que mineurs. Cette thèse est une étude plus précise de ces notions dans le cas de l'interdiction de trois familles, à savoir les circuits de différents types, les prismes et les petites grilles. Nous en déduisons d'une part des bornes polynomiales pour la largeur d'arborescence de certaines familles de graphes et certaines propriétés d'Erdos-Posa et d'autre part de nouveaux algorithmes polynomiaux

La propriete de projection a ete introduite par ernest corominas pour les ensembles ordonnes : un ensemble ordonne est 2-projectif si les projections sont ses seules operations binaires, croissantes et identiques sur la diagonale. L'objet de cette these est l'etude d'extensions de cette notion, a des operations d'arite superieure (projectivite de hamming finie et projectivite cartesienne infinie) et a des structures plus generales. Notre etude des proprietes de projection de hamming (relatives a des operations regulieres par rapport a chaque argument) est fondee sur des idees de topologie algebrique de base. Nous introduisons divers complexes de chaines, dont les proprietes nous fournissent des criteres de projectivite. Ainsi, nous etablissons par exemple, qu'un graphe fini, connexe, sans sommet pendant, est hamming 2-projectif des qu'il n'a ni triangle ni carre, et plus generalement pour n>2, qu'il est hamming n-projectif, quand il n'a pas cycle de longueur inferieure ou egale a n + 1 et qu'il n'est pas lui-meme un cycle. En particulier, cela fournit les premiers exemples de graphes verifiant la propriete de 3-projection de hamming. Notre point de vue va egalement nous permettre d'introduire les proprietes de n-projection simple et double. Notre approche des proprietes de projection infinies (relatives a des operations infinitaires) est de nature plus ensembliste. Nous montrons en particulier, qu'un graphe projectif de diametre fini est denombrablement projectif, des qu'il n'est pas compact pour les systemes atomiques a un nombre fini d'inconnues. Cette these est partagee en sept chapitres regroupes en trois parties. La premiere est consacree a l'expose de generalites. Nous y etablissons egalement la projectivite de certaines structures homogenes, qui nous permettront d'illustrer la suite de notre propos. Dans une seconde partie, nous mettons en place un cadre algebrique pour l'etude des proprietes de projection de hamming. Dans la troisieme, nous etudions des proprietes de projection infinie, que nous illustrons notamment par les exemples des shift-graphs et des structures homogenes.

Presentation d'une methode de recherche d'algorithmes de test des proprietes de graphes d'attributs engendres. Sont decrits, sous forme de point fixe d'un systeme regulier, des algorithmes iteratifs pour les tests de non-circularite, d'existence d'attributs inutiles et d'existence de chemins hamiltoniens dans les graphes engendres

Ce travail étudie des propriétés topologiques des graphes et leurs applications aux réseaux de communications, notamment aux graphes représentant structure d'Internet. Dans un premier temps, on s'intéresse à l'arborescence des graphes par l'étude de deux paramètres : l'hyperbolicité et la largeur arborescente (treewidth). Pour l' hyperbolicité, on analyse sa relation avec d'autres paramètres de graphes et on montre que certaines décompositions de graphes en permettent un calcul efficace. On calcule ces deux paramètres dans des instantanés d'Internet pour différents niveaux hiérarchiques et différentes périodes de temps. On y apporte des interprétations structurelles et algorithmiques pour les valeurs obtenues. On aborde ensuite le problème de partitionnement de graphes (clustering) sous l'angle de la modularité, paramètre qui mesure la qualité d'un partitionnement, largement utilisé dans la littérature. On analyse la modularité du point de vue théorique et son comportement asymptotique pour certaines familles de graphes. Enfin, on s'intéresse à une approche comminatoire de la théorie des files d'attente où les injections de paquets sont effectuées par un adversaire. On propose une généralisation de ce modèle par l'introduction de différentes classes de requêtes<br>This thesis focuses on topological properties of graphs and their application on communication networks, specifically on graphs reflecting Internet structure. We first look how far from a tree a graph may be by the study of two parameters: hyperbolicity and treewidth. For hyperbolicity, we analyse the relation with others graph parameters, we also show that some graph decompositions allow its efficient computation. We compute both parameters o Internet snapshots at different levels of granularity and time periods. We propose some structural and algorithmic consequences of obtained values. Then, we study the graph clustering problem from the perspective of modularity, which measures a clustering quality and is largely studied in the literature. We analyse modularity from a theoretical point of view and [describe] its asymptotic behaviour for some graph families. Finally, we deal with adversarial queueing theory, a combinatorial framework derived from classic queueing theory where injection process is und the control of an adversary. We propose a new model generalisation by considering request of distinct types