Siga este link para ver outros tipos de publicações sobre o tema: Graphe complet.
Teses / dissertações sobre o tema "Graphe complet"
Crie uma referência precisa em APA, MLA, Chicago, Harvard, e outros estilos
Veja os 50 melhores trabalhos (teses / dissertações) para estudos sobre o assunto "Graphe complet".
Ao lado de cada fonte na lista de referências, há um botão "Adicionar à bibliografia". Clique e geraremos automaticamente a citação bibliográfica do trabalho escolhido no estilo de citação de que você precisa: APA, MLA, Harvard, Chicago, Vancouver, etc.
Você também pode baixar o texto completo da publicação científica em formato .pdf e ler o resumo do trabalho online se estiver presente nos metadados.
Veja as teses / dissertações das mais diversas áreas científicas e compile uma bibliografia correta.
1
Cornet, Alexis. "Algorithmes et résultats de complexité pour des problèmes de graphes avec contraintes additionnelles." Thesis, Université Clermont Auvergne (2017-2020), 2018. http://www.theses.fr/2018CLFAC034/document.
Texto completo da fonteResumo:
Les problèmes de domination (dominant, dominant indépendant, ...) et de couverture (vertex-cover, arbre de Steiner, ...) sont NP-complets. Pour autant, pour la plupart de ces problèmes, il existe toujours une solution constructible en temps polynomial (potentiellement de valeur objective très mauvaise), ou au moins, il est possible de déterminer facilement (en temps polynomial) l'existence ou non d'une solution. Ces problèmes, initialement issus de situations réelles, sont des modélisations simplistes de ces situations. Nous ajoutons donc des contraintes additionnelles modélisant des contraintes pratiques plausibles : les conflits, des paires d'éléments ne pouvant faire simultanément partie d'une solution (modélisant des incompatibilités diverses), la connexité dans un second graphe (les éléments doivent pouvoir communiquer, et le graphe correspondant à ces liens de communication n'est pas forcément le même) et les obligations, des sous-ensembles d'éléments interdépendants devant être ajoutés simultanément à une solution. Notre but ici n'est pas de modéliser un problème réel précis, mais d'étudier la manière dont ces contraintes modifient la complexité des problèmes étudiés. Nous verrons que dans un grand nombre de cas, déterminer l'existence même d'une solution devient difficile, même sans se préoccuper de leur optimisation. Le problème du firefighter modélise des pompiers tentant de contenir un feu se propageant au tour par tour dans un graphe (potentiellement infini). Nous avons étudié ce problème en ajoutant des contraintes sur le déplacement des pompiers (une vitesse de déplacement limitée entre deux tours). Nous verrons que ces contraintes augmentent en général le nombre de pompiers nécessaires mais ne provoquent pas de changements aussi importants que dans les problèmes précédents<br>Domination problems (dominating set, independant dominating set, ...) as well as covering problems (vertex-cover, Steiner tree, ...) are NP-complete. However, for most of these problems, it is always possible to construct a (eventually bad) solution in polynomial time, or at least it is possible to determine whether a solution exists. Those problems originally came from industry, but are simplified modelizations of the real life problems. We add additional constraints modeling plausible practical constraints : conflicts which are pairs of elements that cannot apear simultaneously in a solution (to modelize various incompatibilities), connexity in a second graph (elements of the solution must be able to communicate, and the communication links are a second graph), and obligations which are subsets of interdependant vertices which must be added simultaneously in a solution.We don't aim to model a specific real-world problem, but to study how these plausible constraints affect the complexity of the studied problems. We will see that, in many cases, even determining the existence of a solution (regardless of its size) become hard. The firefighter problem models firefighters aiming to contain a fire spreading turn by turn in a (eventually infinite) graph. We studied this problem with the addition of deplacement constraints for the firefighters (a limited moving speed between turns). We will see that, most of the time, this constraint increase the number of firefighters necessary to contain the fire, but does not trigger such major change as constraints studied in the others problems
2
Ghaemi, Mohammadreza. "Etude de la complexité algorithmique associée à des opérations de décomposition de graphes." Paris 6, 2008. http://www.theses.fr/2008PA066449.
Texto completo da fonteResumo:
La thèse porte sur des problèmes de complexitè liés à des opération de décomposition de graphes. Etant donné un graphe donné H (clique, stable, biparti, graphe à seuil) et un graphe G n-apparié, on étudie la complexité algorithmique du problème suivant : Existe-t-il un sous-graphe induit de G qui contient exactement un sommet de chacune des n paires de G isomorphe à H?. On montrera enfin que le problème de décomposition des graphes appelés graphes Stubborn est équivalent au problème précédent pour un cas particulier de graphes n-appariés.
3
Sima, Xingyu. "La gestion des connaissances dans les petites et moyennes entreprises : un cadre adapté et complet." Electronic Thesis or Diss., Université de Toulouse (2023-....), 2024. http://www.theses.fr/2024TLSEP047.
Texto completo da fonteResumo:
La connaissance est essentielle pour les organisations, particulièrement dans le contexte de l'Industrie 4.0. La Gestion des Connaissances (GC) joue un rôle critique dans le succès des organisations. Bien que la GC ait été relativement bien étudiée dans les grandes organisations, les Petites et Moyennes Entreprises (PMEs) reçoivent moins d'attention. Les PMEs font face à des défis uniques en termes de GC, nécessitant un cadre de GC dédié. Notre étude vise à définir un cadre répondant à leurs défis tout en tirant parti de leurs forces inhérentes. Cette thèse présente un cadre de GC dédié et complet pour les PMEs, offrant des solutions dédiées pour l’ensemble des activités de GC, de l'acquisition et la représentation des connaissances à leur exploitation: (1) un processus d'acquisition de connaissances dédié basé sur le cadre Scrum, une méthodologie agile, (2) un modèle de représentation des connaissances dédié basé sur des graphes de connaissances semi-structurés, et (3) un processus d'exploitation des connaissances dédié basé sur le système de recommandation établi sur les liens entre les connaissances. Cette recherche a été menée en collaboration avec Axsens-bte, une PME spécialisée dans le conseil et la formation. Le partenariat avec Axsens-bte a fourni des retours précieux et des expériences pratiques, contribuant au développement du cadre de GC proposé et soulignant sa pertinence et son applicabilité dans des contextes réels de PME<br>Knowledge is vital for organizations, particularly in today’s Industry 4.0 context. Knowledge Management (KM) plays a critical role in an organization's success. Although KM has been relatively well-studied in large organizations, Small and Medium-sized Enterprises (SMEs) receive less attention. SMEs face unique challenges in KM, requiring a tailored KM framework. Our study aims to define a framework addressing their challenges while leveraging their inherent strengths. This thesis presents a dedicated and comprehensive SME KM framework, offering dedicated solutions from knowledge acquisition and representation to exploitation: (1) a dedicated knowledge acquisition process based on the Scrum framework, an agile methodology, (2) a dedicated knowledge representation model based on semi-structured KG, and (3) a dedicated knowledge exploitation process based on knowledge-relatedness RS. This research was conducted in collaboration with Axsens-bte, an SME specializing in consultancy and training. The partnership with Axsens-bte has provided invaluable insights and practical experiences, contributing to developing the proposed KM framework and highlighting its relevance and applicability in real-world SME contexts
4
Culus, Jean-François. "Décompositions acircuituques de grands graphes orientés:des apsects algorithmiques aux aspects combinatoires." Phd thesis, Université Toulouse le Mirail - Toulouse II, 2006. http://tel.archives-ouvertes.fr/tel-00134814.
Texto completo da fonteResumo:
Ce travail de thèse s'inscrit dans le domaine de la recherche de structures dans un graphe. <br />On étudie certaines propriétés algorithmiques et combinatoires pour successivement trois types de colorations : orientée, mixte et décomposition acircuitique. <br />Pour la coloration orientée, on obtient des résultats de NP-complétude pour des classes de graphes très spécifiques ainsi que des résultats d'inapproximabilité. Pour dépasser ces difficultés, nous définissons une notion de coloration mixte et obtenons un résultat d'approximation différentielle ainsi qu'une interprétation du polynôme chromatique mixte qui généralise le résultat de Stanley pour certains graphes mixtes. En relachant la contrainte de classe monochromatique stable, nous étudions finalement la complexité de la décomposition acircuitique, caractérisons une famille de tournoi critique indécomposable et établissons les premières propriétés du polynôme chromatique acircuitique.
5
Glorieux, Antoine. "Optimizing the imbalances in a graph." Thesis, Evry, Institut national des télécommunications, 2017. http://www.theses.fr/2017TELE0011/document.
Texto completo da fonteResumo:
Le déséquilibre d'un sommet dans un graphe orienté est la valeur absolue de la différence entre son degré sortant et son degré entrant. Nous étudions le problème de trouver une orientation des arêtes du graphe telle que l'image du vecteur dont les composantes sont les déséquilibres des sommets par une fonction objectif f est maximisée. Le premier cas considéré est le problème de maximiser le minimum des déséquilibres sur toutes les orientations possibles. Nous caractérisons les graphes dont la valeur objective optimale est nulle. Ensuite nous donnons plusieurs résultats concernant la complexité du problème. Enfin, nous introduisons différentes formulations du problème et présentons quelques résultats numériques. Par la suite, nous montrons que le cas f=1/2 | |·| |₁ mène au célèbre problème de la coupe de cardinalité maximale. Nous introduisons de nouvelles formulations ainsi qu'un nouveau majorant qui domine celui de Goemans et Williamson. Des résultats théoriques et numériques concernant la performance des approches sont présentés. Pour finir, dans le but de renforcer certaines des formulations des problèmes étudiés, nous étudions une famille de polyèdres spécifique consistant en l'enveloppe convexe des matrices d'affectation 0/1 (où chaque colonne contient exactement une composante égale à 1) annexée avec l'indice de leur ligne non-identiquement nulle la plus basse. Nous donnons une description complète de ce polytope ainsi que certaines de ses variantes qui apparaissent naturellement dans le contexte de divers problèmes d'optimisation combinatoire. Nous montrons également que résoudre un programme linéaire sur un tel polytope peut s'effectuer en temps polynomial<br>The imbalance of a vertex in a directed graph is the absolute value of the difference between its outdegree and indegree. In this thesis we study the problem of orienting the edges of a graph in such a way that the image of the vector which components are the imbalances of the vertices of the graph under an objective function f is maximized. The first case considered is the problem of maximizing the minimum imbalance of all the vertices over all the possible orientations of the input graph. We first characterize graphs for which the optimal objective value is zero. Next we give several results concerning the computational complexity of the problem. Finally, we deal with several mixed integer programming formulations for this problem and present some numerical experiments. Next, we show that the case for f=1/2 | |·| |₁ leads to the famous unweighted maximum cut problem. We introduce some new formulations along with a new bound shown to be tighter than Michel Goemans & David Williamson's. Theoretical and computational results regarding bounds quality and performance are also reported. Finally, in order to strengthen some formulations of the studied problems, we study a specific class of polytopes. Consider the polytope consisting in the convex hull of the 0/1 assignment matrices where each column contains exactly one coefficient equal to 1 appended with their index of the lowest row that is not identically equal to the zero row. We give a full description of this polytope and some of its variants which naturally appear in the context of several combinatorial optimization problems. We also show that linear optimization over those polytopes can be done in polynomial time
6
Glorieux, Antoine. "Optimizing the imbalances in a graph." Electronic Thesis or Diss., Evry, Institut national des télécommunications, 2017. http://www.theses.fr/2017TELE0011.
Texto completo da fonteResumo:
Le déséquilibre d'un sommet dans un graphe orienté est la valeur absolue de la différence entre son degré sortant et son degré entrant. Nous étudions le problème de trouver une orientation des arêtes du graphe telle que l'image du vecteur dont les composantes sont les déséquilibres des sommets par une fonction objectif f est maximisée. Le premier cas considéré est le problème de maximiser le minimum des déséquilibres sur toutes les orientations possibles. Nous caractérisons les graphes dont la valeur objective optimale est nulle. Ensuite nous donnons plusieurs résultats concernant la complexité du problème. Enfin, nous introduisons différentes formulations du problème et présentons quelques résultats numériques. Par la suite, nous montrons que le cas f=1/2 | |·| |₁ mène au célèbre problème de la coupe de cardinalité maximale. Nous introduisons de nouvelles formulations ainsi qu'un nouveau majorant qui domine celui de Goemans et Williamson. Des résultats théoriques et numériques concernant la performance des approches sont présentés. Pour finir, dans le but de renforcer certaines des formulations des problèmes étudiés, nous étudions une famille de polyèdres spécifique consistant en l'enveloppe convexe des matrices d'affectation 0/1 (où chaque colonne contient exactement une composante égale à 1) annexée avec l'indice de leur ligne non-identiquement nulle la plus basse. Nous donnons une description complète de ce polytope ainsi que certaines de ses variantes qui apparaissent naturellement dans le contexte de divers problèmes d'optimisation combinatoire. Nous montrons également que résoudre un programme linéaire sur un tel polytope peut s'effectuer en temps polynomial<br>The imbalance of a vertex in a directed graph is the absolute value of the difference between its outdegree and indegree. In this thesis we study the problem of orienting the edges of a graph in such a way that the image of the vector which components are the imbalances of the vertices of the graph under an objective function f is maximized. The first case considered is the problem of maximizing the minimum imbalance of all the vertices over all the possible orientations of the input graph. We first characterize graphs for which the optimal objective value is zero. Next we give several results concerning the computational complexity of the problem. Finally, we deal with several mixed integer programming formulations for this problem and present some numerical experiments. Next, we show that the case for f=1/2 | |·| |₁ leads to the famous unweighted maximum cut problem. We introduce some new formulations along with a new bound shown to be tighter than Michel Goemans & David Williamson's. Theoretical and computational results regarding bounds quality and performance are also reported. Finally, in order to strengthen some formulations of the studied problems, we study a specific class of polytopes. Consider the polytope consisting in the convex hull of the 0/1 assignment matrices where each column contains exactly one coefficient equal to 1 appended with their index of the lowest row that is not identically equal to the zero row. We give a full description of this polytope and some of its variants which naturally appear in the context of several combinatorial optimization problems. We also show that linear optimization over those polytopes can be done in polynomial time
7
Halftermeyer, Pierre. "Connexité dans les Réseaux et Schémas d’Étiquetage Compact d’Urgence." Thesis, Bordeaux, 2014. http://www.theses.fr/2014BORD0140/document.
Texto completo da fonteResumo:
L’objectif de cette thèse est d’attribuer à chaque sommet x d’un graphe G à n sommets une étiquette L(x) de taille compacte O(log n) bits afin de pouvoir :1. construire, à partir des étiquettes d’un ensemble de sommets en panne X C V (G), une structure de donnée S(X)2. décider, à partir de S(X) et des étiquettes L(u) et L(v), si les sommets u et v sont connectés dans le graphe G n X.Nous proposons une solution à ce problème pour la famille des graphes 3-connexes de genre g (via plusieurs résultats intermédiaires).— Les étiquettes sont de taille O(g log n) bits— Le temps de construction de la structure de donnée S(X) est O(Sort([X]; n)).— Le temps de décision est O(log log n). Ce temps est optimal.Nous étendons ce résultat à la famille des graphes excluant un mineur H fixé. Les étiquettes sont ici de taille O(polylog n) bits<br>We aim at assigning each vertex x of a n-vertices graph G a compact O(log n)-bit label L(x) in order to :1. construct, from the labels of the vertices of a forbidden set X C V (G), a datastructure S(X)2. decide, from S(X), L(u) and L(v), whether two vertices u and v are connected in G n X.We give a solution to this problem for the family of 3-connected graphs whith bounded genus.— We obtain O(g log n)-bit labels.— S(X) is computed in O(Sort([X]; n)) time.— Connection between vertices is decided in O(log log n) optimal time.We finally extend this result to H-minor-free graphs. This scheme requires O(polylog n)-bit labels
8
Islam, Md Kamrul. "Explainable link prediction in large complex graphs - application to drug repurposing." Electronic Thesis or Diss., Université de Lorraine, 2022. http://www.theses.fr/2022LORR0203.
Texto completo da fonteResumo:
De nombreux systèmes complexes du monde réel peuvent être représentés par des graphes, où les nœuds représentent des entités et les liens des relations entre les paires de nœuds. La prédiction de liens (LP) est l'un des problèmes les plus intéressants et les plus anciens dans le domaine de l'exploration de graphes ; elle prédit la probabilité d'un lien entre deux nœuds non connectés. Cette thèse étudie le problème LP dans les graphes simples et les graphes de connaissances (KGs). La première partie de cette thèse se concentre sur le problème LP dans les graphes simples. Dans la première étude, des approches basées sur la similarité et sur l'encastrement sont évaluées et comparées sur des graphes simples de différents domaines. L'étude a également identifié la difficulté de fixer le seuil du score de similarité pour calculer la métrique de précision des approches basées sur la similarité et a proposé une nouvelle méthode pour calculer la métrique. Les résultats ont montré la supériorité attendue des approches basées sur l'intégration. Cependant, chaque approche basée sur la similarité s'est avérée compétitive sur des graphes aux propriétés spécifiques. Nous avons pu vérifier expérimentalement que les approches basées sur la similarité sont explicables mais manquent de généralisation, tandis que les approches basées sur l'encastrement sont générales mais non explicables. La deuxième étude tente de surmonter la limitation de l'inexplicabilité des approches basées sur l'encastrement en découvrant des connexions intéressantes entre elles et les approches basées sur la similarité. La troisième étude démontre comment les approches basées sur la similarité peuvent être assemblées pour concevoir une approche LP supervisée explicable. Il est intéressant de noter que l'étude montre des performances LP élevées pour l'approche supervisée sur différents graphes, ce qui est très satisfaisant. La deuxième partie de la thèse se concentre sur les LP dans les KGs. Un KG est représenté comme une collection de triplets RDF, (head,relation,tail) où les entités head et tail sont reliées par une relation spécifique. Le problème de LP dans un KG est formulé comme la prédiction de la tête ou de la queue manquante dans un triplet. La LP basée sur l'incorporation de KG est devenue très populaire ces dernières années, et la génération de triplets négatifs est une tâche importante dans les méthodes d'incorporation. La quatrième étude traite d'une nouvelle méthode appelée SNS pour générer des triplets négatifs de haute qualité. Nos résultats montrent une meilleure performance LP lorsque SNS est utilisé que lorsque d'autres méthodes d'échantillonnage négatif sont utilisées. La deuxième étude traite d'une nouvelle méthode d'extraction de règles neuro-symboliques et d'une stratégie d'abduction pour expliquer les LP par une approche basée sur l'intégration en utilisant les règles apprises. La troisième étude applique notre LP explicable pour développer une nouvelle approche de repositionnement des médicaments pour COVID-19. L'approche apprend un ensemble d'enchâssements d'entités et de relations dans un KG centré sur COVID-19 pour obtenir un meilleur enchâssement des éléments du graphe. Pour la première fois à notre connaissance, des méthodes de criblage virtuel sont ensuite utilisées pour évaluer les prédictions obtenues à l'aide des embeddings. L'évaluation moléculaire et les chemins explicatifs apportent de la fiabilité aux résultats de prédiction et sont de nouvelles méthodes complémentaires et réutilisables pour mieux évaluer les molécules proposées pour le repositionnement. La dernière étude propose une architecture distribuée pour l'apprentissage des KG embeddings dans des environnements distribués et parallèles. Les résultats révèlent que l'apprentissage dans l'environnement distribué proposé, par rapport à un apprentissage centralisé, réduit considérablement le temps de calcul des méthodes d'incorporation KG sans affecter les performances des LP<br>Many real-world complex systems can be well-represented with graphs, where nodes represent objects or entities and links/relations represent interactions between pairs of nodes. Link prediction (LP) is one of the most interesting and long-standing problems in the field of graph mining; it predicts the probability of a link between two unconnected nodes based on available information in the current graph. This thesis studies the LP problem in graphs. It consists of two parts: LP in simple graphs and LP knowledge graphs (KGs). In the first part, the LP problem is defined as predicting the probability of a link between a pair of nodes in a simple graph. In the first study, a few similarity-based and embedding-based LP approaches are evaluated and compared on simple graphs from various domains. he study also criticizes the traditional way of computing the precision metric of similarity-based approaches as the computation faces the difficulty of tuning the threshold for deciding the link existence based on the similarity score. We proposed a new way of computing the precision metric. The results showed the expected superiority of embedding-based approaches. Still, each of the similarity-based approaches is competitive on graphs with specific properties. We could check experimentally that similarity-based approaches are fully explainable but lack generalization due to their heuristic nature, whereas embedding-based approaches are general but not explainable. The second study tries to alleviate the unexplainability limitation of embedding-based approaches by uncovering interesting connections between them and similarity-based approaches to get an idea of what is learned in embedding-based approaches. The third study demonstrates how the similarity-based approaches can be ensembled to design an explainable supervised LP approach. Interestingly, the study shows high LP performance for the supervised approach across various graphs, which is competitive with embedding-based approaches.The second part of the thesis focuses on LP in KGs. A KG is represented as a collection of RDF triples, (head,relation,tail) where the head and the tail are two entities which are connected by a specific relation. The LP problem in a KG is formulated as predicting missing head or tail entities in a triple. LP approaches based on the embeddings of entities and relations of a KG have become very popular in recent years, and generating negative triples is an important task in KG embedding methods. The first study in this part discusses a new method called SNS to generate high-quality negative triples during the training of embedding methods for learning embeddings of KGs. The results we produced show better LP performance when SNS is injected into an embedding approach than when injecting state-of-the-art negative triple sampling methods. The second study in the second part discusses a new neuro-symbolic method of mining rules and an abduction strategy to explain LP by an embedding-based approach utilizing the learned rules. The third study applies the explainable LP to a COVID-19 KG to develop a new drug repurposing approach for COVID-19. The approach learns ”ensemble embeddings” of entities and relations in a COVID-19 centric KG, in order to get a better latent representation of the graph elements. For the first time to our knowledge, molecular docking is then used to evaluate the predictions obtained from drug repurposing using KG embedding. Molecular evaluation and explanatory paths bring reliability to prediction results and constitute new complementary and reusable methods for assessing KG-based drug repurposing. The last study proposes a distributed architecture for learning KG embeddings in distributed and parallel settings. The results of the study that the computational time of embedding methods improves remarkably without affecting LP performance when they are trained in the proposed distributed settings than the traditional centralized settings
9
Dieng, Youssou. "Décomposition arborescente des graphes planaires et routage compact." Thesis, Bordeaux 1, 2009. http://www.theses.fr/2009BOR13855/document.
Texto completo da fonteResumo:
Savoir comment transmettre une information est fondamental dans un réseau. Il est essentiel que chaque entité du réseau soit capable de décider localement, avec sa vue du réseau, du chemin par lequel l'information doit passer. Ainsi, il est souvent utile d'étudier la topologie du réseau, modélisée par un graphe, pour répondre à ces exigences. Nous nous intéressons dans un premier temps, à la décomposition arborescente des graphes planaires. En effet, comme dans beaucoup de problèmes de graphes, l'étude de la topologie des graphes nous conduit à procéder à une décomposition du graphe afin d'exploiter les propriétés structurelles qui en découlent. En suite, nous nous sommes aussi intéressés à la structure des graphes qui excluent un mineur H, en particulier le graphe K_{2,r}. Ces travaux nous ont permis d'améliorer les bornes actuelles connues sur la largeur arborescente de ces graphes. Dans la dernière partie, nous abordons le problème du routage compact. Nous nous sommes intéressés aux schémas de routage de plus courts chemins utilisant des adresses, des tables de routage de tailles optimales de O(log n) bits, où n est le nombre de sommets du graphe. Nous proposons un tel schéma de routage pour une famille de graphes valués contenant les arbres et les graphes planaire-extérieurs<br>In a network, it is crucial to know how to construct an efficent routing scheme. It is fundamental for each entity with its local knowledge of the network, to be able to decide on which link to forward messages. Thus, it is important to sutdy the underlying network topology in order to design routing schemes. In the first part of this thesis, we construct a new tree-decomposition for planar graphs. In fact, as in many graph problems, the study of the graph structure leads to do a tree-decomposition for exploiting structural propertys of the graphs. In second part, we studied the structure of H-minor free graphs, in particular whenever H = K_{2,r}. Our results improve upon previous known bounds about the tree-width of K_{2,r}-minor free graphs. At last, we treat the problème of compact routing scheme. More precisely, we are interested in shortest-path routing schemes that use O(\log n) bits for addresses, headers and routing tables, where n is the number of vertices in the graph. We propose such a routing scheme for a large family of weighted graphs including outerplanar graphs
10
Allagan, Julian Apelete D. Johnson Peter D. "Choice numbers, Ohba numbers and Hall numbers of some complete k-partite graphs." Auburn, Ala, 2009. http://hdl.handle.net/10415/1780.
Texto completo da fonte
11
Sehgal, Nidhi Rodger C. A. "4-cycles systems of line graphs of complete multipartite graphs." Auburn, Ala, 2008. http://repo.lib.auburn.edu/EtdRoot/2008/SUMMER/Mathematics_and_Statistics/Thesis/Sehgal_Nidhi_47.pdf.
Texto completo da fonte
12
Rocha, Mário. "The embedding of complete bipartite graphs onto grids with a minimum grid cutwidth." CSUSB ScholarWorks, 2003. https://scholarworks.lib.csusb.edu/etd-project/2311.
Texto completo da fonte
13
Onyumbe, Okitowamba. "Groupoids of homogeneous factorisations of graphs /." Online access, 2008. http://etd.uwc.ac.za/usrfiles/modules/etd/docs/etd_gen8Srv25Nme4_9246_1278010591.pdf.
Texto completo da fonte
14
Uduman, Mohamed. "Identifying the largest complete data set from ALFRED /." Link to online version, 2006. https://ritdml.rit.edu/dspace/handle/1850/1876.
Texto completo da fonte
15
Tremblay, Nicolas. "Réseaux et signal : des outils de traitement du signal pour l'analyse des réseaux." Thesis, Lyon, École normale supérieure, 2014. http://www.theses.fr/2014ENSL0938/document.
Texto completo da fonteResumo:
Cette thèse propose de nouveaux outils adaptés à l'analyse des réseaux : sociaux, de transport, de neurones, de protéines, de télécommunications... Ces réseaux, avec l'essor de certaines technologies électroniques, informatiques et mobiles, sont de plus en plus mesurables et mesurés ; la demande d'outils d'analyse assez génériques pour s'appliquer à ces réseaux de natures différentes, assez puissants pour gérer leur grande taille et assez pertinents pour en extraire l'information utile, augmente en conséquence. Pour répondre à cette demande, une grande communauté de chercheurs de différents horizons scientifiques concentre ses efforts sur l'analyse des graphes, des outils mathématiques modélisant la structure relationnelle des objets d'un réseau. Parmi les directions de recherche envisagées, le traitement du signal sur graphe apporte un éclairage prometteur sur la question : le signal n'est plus défini comme en traitement du signal classique sur une topologie régulière à n dimensions, mais sur une topologie particulière définie par le graphe. Appliquer ces idées nouvelles aux problématiques concrètes d'analyse d'un réseau, c'est ouvrir la voie à une analyse solidement fondée sur la théorie du signal. C'est précisément autour de cette frontière entre traitement du signal et science des réseaux que s'articule cette thèse, comme l'illustrent ses deux principales contributions. D'abord, une version multiéchelle de détection de communautés dans un réseau est introduite, basée sur la définition récente des ondelettes sur graphe. Puis, inspirée du concept classique de bootstrap, une méthode de rééchantillonnage de graphes est proposée à des fins d'estimation statistique<br>This thesis describes new tools specifically designed for the analysis of networks such as social, transportation, neuronal, protein, communication networks... These networks, along with the rapid expansion of electronic, IT and mobile technologies are increasingly monitored and measured. Adapted tools of analysis are therefore very much in demand, which need to be universal, powerful, and precise enough to be able to extract useful information from very different possibly large networks. To this end, a large community of researchers from various disciplines have concentrated their efforts on the analysis of graphs, well define mathematical tools modeling the interconnected structure of networks. Among all the considered directions of research, graph signal processing brings a new and promising vision : a signal is no longer defined on a regular n-dimensional topology, but on a particular topology defined by the graph. To apply these new ideas on the practical problems of network analysis paves the way to an analysis firmly rooted in signal processing theory. It is precisely this frontier between signal processing and network science that we explore throughout this thesis, as shown by two of its major contributions. Firstly, a multiscale version of community detection in networks is proposed, based on the recent definition of graph wavelets. Then, a network-adapted bootstrap method is introduced, that enables statistical estimation based on carefully designed graph resampling schemes
16
Knopp, Sebastian. "Complex Job-Shop Scheduling with Batching in Semiconductor Manufacturing." Thesis, Lyon, 2016. http://www.theses.fr/2016LYSEM014/document.
Texto completo da fonteResumo:
La prise en compte de machines à traitement par batch dans les problèmes d’ordonnancement d’ateliers complexes de type job-shop est particulièrement difficile. La fabrication de semiconducteurs est probablement l’une des applications pratiques les plus importantes pour ce types de problèmes. Nous considérons un problème d’ordonnancement de type job-shop flexible avec « p-batching », des flux rentrants, des temps de préparation dépendant de la séquence et des dates de début au plus tôt. Le but c’est d’optimiser différentes fonctions objectives régulières.Les approches existantes par graphe disjonctif pour ce problème utilise des nœuds dédiés pour représenter explicitement les batches. Afin de faciliter la modification du graphe conjonctif, notre nouvelle modélisation réduit cette complexité en modélisant les décisions de batching à travers les poids des arcs. Une importante contribution de cette thèse est un algorithme original qui prend les décisions de batching lors du parcours du graphe. Cet algorithme est complété par un déplacement (« move ») intégré qui permet de reséquencer ou réaffecter les opérations. Cette combinaison donne un voisinage riche que nous appliquons dans une approche méta-heuristique de type GRASP.Nous étendons cette approche en prenant en compte de nouvelles contraintes qui ont un rôle important dans l’application industrielle considérée. En particulier, nous modélisons de manière explicite les ressources internes des machines, et nous considérons un temps maximum d’attente entre deux opérations quelconques d’une gamme de fabrication. Les résultats numériques sur des instances de la littérature pour des problèmes plus simples ainsi que sur de nouvelles instances montrent la généricité et l’applicabilité de notre approche. Notre nouvelle modélisation permet de faciliter les extensions à d’autres contraintes complexes rencontrées dans les applications industrielles<br>The integration of batching machines within a job-shop environment leads to a complex job-shop scheduling problem. Semiconductor manufacturing presumably represents one of the most prominent practical applications for such problems. We consider a flexible job-shop scheduling problem with p-batching, reentrant flows, sequence dependent setup times and release dates while considering different regular objective functions. The scheduling of parallel batching machines and variants of the job-shop scheduling problem are well-studied problems whereas their combination is rarely considered.Existing disjunctive graph approaches for this combined problem rely on dedicated nodes to explicitly represent batches. To facilitate modifications of the graph, our new modeling reduces this complexity by encoding batching decisions into edge weights. An important contribution is an original algorithm that takes batching decisions “on the fly” during graph traversals. This algorithm is complemented by an integrated move to resequence and reassign operations. This combination yields a rich neighborhood that we apply within a GRASP based metaheuristic approach.We extend this approach by taking further constraints into account that are important in the considered industrial application. In particular, we model internal resources of machines in detail and take maximum time lag constraints into account. Numerical results for benchmark instances of different problem types show the generality and applicability of our approach. The conciseness of our idea facilitates extensions towards further complex constraints needed in real-world applications
17
Rafla, Nabil H. "The good drawings D r of the complete graph K r /." Thesis, McGill University, 1988. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=75756.
Texto completo da fonteResumo:
This thesis treats some of the problems related to the good drawings D$ sb{ rm n}$ of the complete graph K$ sb{ rm n}$. The first of these problems is obtaining all the non-isomorphic good drawings D$ sb{ rm n}$ of K$ sb{ rm n}$. After conjecturing that any good drawing D$ sb{ rm n}$ of K$ sb{ rm n}$ has at least one crossing-free Hamiltonian Circuit, an algorithm generating all the non-isomorphic good drawings D$ sb{ rm n}$ of K$ sb{ rm n}$ is developed. The second problem, determining the existence of a rectilinear drawing D$ sb{ rm n}$ of K$ sb{ rm n}$ with a given set of crossings, is solved by finding a characteristic of the rectilinear drawings D$ sb{ rm n}$ of K$ sb{ rm n}$. An algorithm using this characteristic determines whether a given set of crossing defines a rectilinear drawing D$ sb{ rm n}$ of K$ sb{ rm n}$. The last problem, to generate all the non-isomorphic rectilinear drawings D$ sb{ rm n}$ of K$ sb{ rm n}$, is solved by an algorithm using a set of rectilinear drawings D$ sb{ rm n-1}$ of K$ sb{ rm n-1}$.
18
Boudermine, Antoine. "A dynamic attack graphs based approach for impact assessment of vulnerabilities in complex computer systems." Electronic Thesis or Diss., Institut polytechnique de Paris, 2022. http://www.theses.fr/2022IPPAT046.
Texto completo da fonteResumo:
De nos jours, les réseaux informatiques sont utilisés dans de nombreux domaines et leur défaillance peut avoir un fort impact sur notre vie quotidienne. L'évaluation de leur sécurité est une nécessité pour réduire le risque de compromission par un attaquant. Néanmoins, les solutions proposées jusqu'à présent sont rarement adaptées à la grande complexité des systèmes informatiques modernes. Elles reposent souvent sur un travail humain trop important et les algorithmes utilisés ne sont pas assez performants. De plus, l'évolution du système dans le temps est rarement modélisée et n'est donc pas prise en compte dans l'évaluation de sa sécurité. Dans cette thèse, nous proposons un nouveau modèle de graphe d'attaque construit à partir d'une description dynamique du système. Nous avons mis en évidence à travers nos expériences que notre modèle permettait d'identifier davantage de chemins d'attaque qu'un modèle de graphe d'attaque statique. Nous avons ensuite proposé un algorithme de simulation d'attaques permettant d'approximer les chances de succès de compromission du système par un acteur malveillant. Nous avons également prouvé que notre solution était capable d'analyser la sécurité de systèmes complexes. La complexité en temps dans le pire des cas a été évaluée pour chaque algorithme utilisé et plusieurs tests ont été réalisés pour mesurer leurs performances réelles. Pour terminer, nous avons appliqué notre solution sur un réseau IT composé de plusieurs milliers d'éléments. De futurs travaux devraient être réalisés pour améliorer les performances de l'algorithme de génération des graphes d'attaque afin de permettre d'analyser des systèmes toujours plus complexes. Des solutions devraient également être trouvées pour faciliter l'étape de modélisation du système qui reste encore à ce jour une tâche difficile à réaliser, surtout par des humains. Enfin, l'algorithme de simulation pourrait être amélioré pour être plus réaliste et tenir compte des réelles capacités de l'attaquant. Il serait également intéressant d'évaluer l'impact des attaques au niveau de l'organisation et de ses processus métiers<br>Nowadays, computer networks are used in many fields and their breakdown can strongly impact our daily life. Assessing their security is a necessity to reduce the risk of compromise by an attacker. Nevertheless, the solutions proposed so far are rarely adapted to the high complexity of modern computer systems. They often rely on too much human work and the algorithms used don't scale well. Furthermore, the evolution of the system over time is rarely modeled and is therefore not considered in the evaluation of its security.In this thesis, we propose a new attack graph model built from a dynamic description of the system. We have shown through our experimentations that our model allows to identify more attack paths than a static attack graph model. We then proposed an attack simulation algorithm to approximate the chances of success of system compromise by a malicious actor.We also proved that our solution was able to analyze the security of complex systems. The worst-case time complexity was assessed for each algorithm used. Several tests were performed to measure their real performances. Finally, we applied our solution on an IT network composed of several thousand elements.Future work should be done to improve the performance of the attack graph generation algorithm in order to analyze increasingly complex systems. Solutions should also be found to facilitate the system modeling step which is still a difficult task to perform, especially by humans. Finally, the simulation algorithm could be improved to be more realistic and take into account the real capabilities of the attacker. It would also be interesting to assess the impact of the attacks on the organization and its business processes
19
Schickinger, Thomas. "Complete subgraphs of random graphs." [S.l. : s.n.], 2002. http://deposit.ddb.de/cgi-bin/dokserv?idn=966629353.
Texto completo da fonte
20
Kumwenda, Khumbo. "Codes, graphs and designs related to iterated line graphs of complete graphs." Thesis, University of the Western Cape, 2011. http://etd.uwc.ac.za/index.php?module=etd&action=viewtitle&id=gen8Srv25Nme4_1742_1320645699.
Texto completo da fonteResumo:
In this thesis, we describe linear codes over prime fields obtained from incidence designs of iterated line graphs of complete graphs Li(Kn) where i = 1, 2. In the binary case, results are extended to codes from neighbourhood designs of the line graphs Li+1(Kn) using certain elementary relations. Codes from incidence designs of complete graphs, Kn, and neighbourhood designs of their line graphs, L1(Kn) (the so-called triangular graphs), have been considered elsewhere by others. We consider codes from incidence designs of L1(Kn) and L2(Kn), and neighbourhood designs of L2(Kn) and L3(Kn). In each case, basic parameters of the codes are determined. Further, we introduce a family of vertex-transitive graphs ôn that are embeddable into the strong product L1(Kn) â K2, of triangular graphs and K2, a class which at first sight may seem unnatural but, on closer look, is a repository of graphs rich with combinatorial structures. For instance, unlike most regular graphs considered here and elsewhere that only come with incidence and neighbourhood designs, ôn also has what we have termed as 6-cycle designs. These are designs in which the point set contains vertices of the graph and every block contains vertices of a 6-cycle in the graph. Also, binary codes from incidence matrices of these graphs have other minimum words in addition to incidence vectors of the blocks. In addition, these graphs have induced subgraphs isomorphic to the family Hn of complete porcupines (see Definition 4.11). We describe codes from incidence matrices of ôn and Hn and determine their parameters.
21
Wassmer, Arnold. "A dual independence complex." [S.l.] : [s.n.], 2005. http://deposit.ddb.de/cgi-bin/dokserv?idn=976684314.
Texto completo da fonte
22
Hamon, Ronan. "Analyse de réseaux temporels par des méthodes de traitement du signal : application au système de vélos en libre-service à Lyon." Thesis, Lyon, École normale supérieure, 2015. http://www.theses.fr/2015ENSL1017/document.
Texto completo da fonteResumo:
Les systèmes de vélos en libre-service sont devenus des éléments indispensables dans les offres de transport urbain des grandes villes mondiales. À partir des données que ces systèmes génèrent, il est possible d'avoir une caractérisation fine de l'utilisation du vélo en milieu urbain, tant sur des problématiques traitant du domaine des transports que des aspects socio-économiques. Comme pour de nombreux domaines profitant de la récente abondance en données permises par les technologies actuelles de communication et de stockage de l'information, les enjeux actuels résident dans le développement de méthodes d'analyse de données efficaces et adaptées aux systèmes étudiés. Cette thèse se propose de répondre à cette problématique, à la fois par des développements méthodologiques et par une application à des données réelles issues du système de vélos en libre-service Vélo'v à Lyon.Le système Vélo'v peut se représenter sous la forme d'un réseau, décrivant un ensemble de relations entre les différentes stations. Cette représentation, valable également pour de nombreux systèmes, permet l'utilisation d'outils pour décrire la structure du réseau basés sur la théorie des graphes. Néanmoins, la prise en compte d'une dynamique temporelle dans l'évolution des systèmes nécessite d'étendre l'analyse à des réseaux temporels, dont la structure évolue au cours du temps. Le parallèle avec le domaine du traitement du signal, dont le but est l'analyse de signaux temporels, amène à considérer des connexions entre la description de l'évolution d'un réseau temporel et celle d'un signal. Ces travaux proposent de considérer une dualité entre les réseaux temporels et les signaux, de sorte que l'analyse dans le domaine des signaux, à l'aide des outils du traitement du signal, permet de caractériser le réseau temporel correspondant.Cette méthodologie, à la frontière entre le traitement du signal et l'analyse des réseaux, est tout d'abord justifiée par l'étude du système Vélo'v, en comparant différentes approches d'analyse de données et les apports de la représentation sous la forme de réseau temporel. Une méthode d'étiquetage des noeuds d'un graphe est ensuite discutée, permettant d'ouvrir la voie vers une dualité entre réseaux et signaux. Cette dualité est étendue aux réseaux temporels, pour lesquels une méthode d'extraction automatique des structures pertinentes au cours du temps est proposée, à travers la décomposition des signaux correspondants<br>Bike-sharing systems have become essential elements in urban transportation systems of many world's big cities. Thanks to the data generated by these systems, it is possible to obtain a precise characterization of urban cycling, both in terms of transportation and socio-economic aspects. Taking advantage of the recent abundance of data allowed by the current technology, the challenges lie in the development of efficient data analysis method, adapted to these systems. This PhD thesis proposes some answers to this issue, first by methodological developments and second by studying real-world data obtained from the bike-sharing system in Lyon, called Vélo'v.The Vélo'v system can be represented as a network, describing a set of relations between the stations spread over the city. This representation, used for many systems, enables the use of tools from network theory to measure the network structure and understand the underlying mechanisms. Nevertheless, taking into account the dynamic evolution of the structure requires an extension of the classical tools to the temporal case. Parallels between this problem and the field of signal processing can be done, and opens the way to the consideration of connections between the description of the dynamics of temporal networks and those of signals. This work introduces a duality between temporal networks and signals, such that the analysis of the signals using the classical tools of signal processing helps to the characterization of the structure of the corresponding network.This methodology, at the juncture between signal processing and network analysis, is first justified by the study of the Vélo'v network, by comparing different data analysis method and the representation of the system as a temporal network. Then, a method to relabel the vertices of the graph according to the topology of the network is discussed, opening up a duality between networks and signals. This duality is then extended to temporal networks: The analysis of the spectral properties of the signals are studied through a fully automated extraction method, enabling the decomposition of relevant network structure over time
23
Brouard, Vianney. "Cell dynamics of multitype populations in oncology and Invasion probability of cooperative parasites in structured host populations." Electronic Thesis or Diss., Lyon, École normale supérieure, 2024. http://www.theses.fr/2024ENSL0037.
Texto completo da fonteResumo:
Cette thèse porte sur l'étude de deux modèles stochastiques liés à des problèmes médicaux. Le premier vise à comprendre le processus épidémique généré par des bactériophages coopératifs dans une population de bactéries résistantes aux antibiotiques. Pour cela, nous introduisons un modèle épidémiologique où les infections sont générées par la coopération de parasites dans une population d'hôtes structurée selon un modèle de configuration. Une transition de phase est observée pour la probabilité d'invasion dépendant du degré de connectivité des sommets et du nombre de parasites générés lors d'une infection d'un hôte. Au seuil critique, la probabilité d'invasion est identifiée comme la probabilité de survie d'un processus de Galton-Watson.Dans le but d'obtenir un modèle biologiquement plus pertinent, nous avons analysé un modèle similaire où une structure spatiale est ajoutée à la population d'hôtes en utilisant un "random geometric graph". Nous avons montré qu'une telle structure spatiale facilite la coopération des parasites. Une transition de phase similaire se produit où au seuil critique, des bornes supérieure et inférieure sont obtenues pour la probabilité d'invasion en tant que probabilités de survie de deux processus de branchement avec coopération.La deuxième question médicale concerne la compréhension de l'évolution de la composition génétique d'une tumeur en formation, en utilisant des processus de naissance et de mort multitypes branchants sur un espace de traits fini. Considérant une évolution neutre et délétère, nous fournissons des résultats au premier ordre asymptotique pour toutes les tailles des sous-populations mutantes. En particulier, nous capturons la stochasticité associée aux tailles des sous-populations mutantes lorsqu'une tumeur est observée cliniquement, et surtout nous caractérisons les chemins évolutifs effectifs, fournissant des informations sur le passé, le présent et le futur de l'évolution tumorale.Au-delà de ce cadre restrictif d'évolution neutre et délétère, nous proposons une nouvelle méthode pour comprendre le premier ordre asymptotique du premier trait mutant sélectif<br>This thesis focuses on the study of two stochastic models related to medical problems. The first one lies on understanding infection spread of cooperating bacteriophages on a structured multi-drug resistant bacterial host population. Motivated by this example, we introduce an epidemiological model where infections are generated by cooperation of parasites in a host population structured on a configuration model. We analysed the invasion probability for which we obtain a phase transition depending on the connectivity degree of the vertices and the offspring number of parasites during an infection of a host. At the critical scaling, the invasion probability is identified as the survival probability of a Galton-Watson process. With the aim to get a biological more relevant model, we analysed a similar model where a spatial structure is added for the host population using a random geometric graph. We have shown that such spatial structure facilitates cooperation of parasites. A similar phase transition occurs where at the same critical scaling the invasion probability is upper and lower bounded by the survival probabilities of two discrete branching processes with cooperation. The second medical question deals with understanding the evolution of the genetic composition of a tumor under carcinogenesis, using multitype birth and death branching process models on a general finite trait space. In the case of neutral and deleterious cancer evolution, we provide first-order asymptotics results on all mutant subpopulation sizes. In particular such results capture the randomness of all cell trait sizes when a tumor is clinically observed, and mostly it allows to characterize the effective evolutionary pathways, providing information on the past, present, and future of tumor evolution.Moving beyond this restrictive neutral and deleterious cancer evolution framework, we provide a new method to understand the first selective mutant trait size
24
Djang, Claire. "Two-Coloring Cycles In Complete Graphs." Oberlin College Honors Theses / OhioLINK, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=oberlin1370618319.
Texto completo da fonte
25
Gillani, Syed. "Semantically-enabled stream processing and complex event processing over RDF graph streams." Thesis, Lyon, 2016. http://www.theses.fr/2016LYSES055/document.
Texto completo da fonteResumo:
Résumé en français non fourni par l'auteur<br>There is a paradigm shift in the nature and processing means of today’s data: data are used to being mostly static and stored in large databases to be queried. Today, with the advent of new applications and means of collecting data, most applications on the Web and in enterprises produce data in a continuous manner under the form of streams. Thus, the users of these applications expect to process a large volume of data with fresh low latency results. This has resulted in the introduction of Data Stream Processing Systems (DSMSs) and a Complex Event Processing (CEP) paradigm – both with distinctive aims: DSMSs are mostly employed to process traditional query operators (mostly stateless), while CEP systems focus on temporal pattern matching (stateful operators) to detect changes in the data that can be thought of as events. In the past decade or so, a number of scalable and performance intensive DSMSs and CEP systems have been proposed. Most of them, however, are based on the relational data models – which begs the question for the support of heterogeneous data sources, i.e., variety of the data. Work in RDF stream processing (RSP) systems partly addresses the challenge of variety by promoting the RDF data model. Nonetheless, challenges like volume and velocity are overlooked by existing approaches. These challenges require customised optimisations which consider RDF as a first class citizen and scale the processof continuous graph pattern matching. To gain insights into these problems, this thesis focuses on developing scalable RDF graph stream processing, and semantically-enabled CEP systems (i.e., Semantic Complex Event Processing, SCEP). In addition to our optimised algorithmic and data structure methodologies, we also contribute to the design of a new query language for SCEP. Our contributions in these two fields are as follows: • RDF Graph Stream Processing. We first propose an RDF graph stream model, where each data item/event within streams is comprised of an RDF graph (a set of RDF triples). Second, we implement customised indexing techniques and data structures to continuously process RDF graph streams in an incremental manner. • Semantic Complex Event Processing. We extend the idea of RDF graph stream processing to enable SCEP over such RDF graph streams, i.e., temporalpattern matching. Our first contribution in this context is to provide a new querylanguage that encompasses the RDF graph stream model and employs a set of expressive temporal operators such as sequencing, kleene-+, negation, optional,conjunction, disjunction and event selection strategies. Based on this, we implement a scalable system that employs a non-deterministic finite automata model to evaluate these operators in an optimised manner. We leverage techniques from diverse fields, such as relational query optimisations, incremental query processing, sensor and social networks in order to solve real-world problems. We have applied our proposed techniques to a wide range of real-world and synthetic datasets to extract the knowledge from RDF structured data in motion. Our experimental evaluations confirm our theoretical insights, and demonstrate the viability of our proposed methods
26
Smith, S. Alex. "Layered percolation on the complete graph." Diss., Restricted to subscribing institutions, 2008. http://proquest.umi.com/pqdweb?did=1619405931&sid=1&Fmt=2&clientId=1564&RQT=309&VName=PQD.
Texto completo da fonte
27
Couturier, Jean-François. "Algorithmes exacts et exponentiels sur les graphes : énumération, comptage et optimisation." Thesis, Université de Lorraine, 2012. http://www.theses.fr/2012LORR0325/document.
Texto completo da fonteResumo:
L'hypothèse qu'un grand nombre de problèmes n'admettent pas d'algorithme (exact et déterministe) polynomial date de l'avènement de la théorie de la NP-complétude dans les années 70. Depuis, de nombreuses théories et techniques algorithmiques se sont développées pour résoudre ces problèmes difficiles le plus efficacement possible. Dans cette thèse, nous nous intéressons aux algorithmes exacts faiblement exponentiels. L'objectif est d'obtenir des algorithmes de complexité 0* (c^n) où n est la taille de la donnée et c une Constante la plus faible possible<br>The assumption that many problems do not admit algorithm (exact and deterministic) polynomial ate of the advent of the theory of NP-completeness in the 70s. Since many theories and algorithmic techniques have been developed to solve these problems difficult as efficiently as possible. In this thesis, we focus on exact algorithms weakly exponential. The objective is to obtain algorithms complexity 0 * (c ^ n) where n is the size of the data and one constant c as small as possible
28
Pan, Shengjun. "On the Crossing Numbers of Complete Graphs." Thesis, University of Waterloo, 2006. http://hdl.handle.net/10012/1174.
Texto completo da fonteResumo:
In this thesis we prove two main results. The Triangle Conjecture asserts that the convex hull of any optimal rectilinear drawing of <em>K<sub>n</sub></em> must be a triangle (for <em>n</em> ≥ 3). We prove that, for the larger class of pseudolinear drawings, the outer face must be a triangle. The other main result is the next step toward Guy's Conjecture that the crossing number of <em>K<sub>n</sub></em> is $(1/4)[n/2][(n-1)/2][(n-2)/2][(n-3)/2]$. We show that the conjecture is true for <em>n</em> = 11,12; previously the conjecture was known to be true for <em>n</em> ≤ 10. We also prove several minor results.
29
Lim, Tian Khoon. "Edge-transitive homogeneous factorisations of complete graphs." University of Western Australia. School of Mathematics and Statistics, 2004. http://theses.library.uwa.edu.au/adt-WU2004.0039.
Texto completo da fonteResumo:
[Formulae and special characters can only be approximated here. Please see the pdf version of the abstract for an accurate reproduction.] This thesis concerns the study of homogeneous factorisations of complete graphs with edge-transitive factors. A factorisation of a complete graph Kn is a partition of its edges into disjoint classes. Each class of edges in a factorisation of Kn corresponds to a spanning subgraph called a factor. If all the factors are isomorphic to one another, then a factorisation of Kn is called an isomorphic factorisation. A homogeneous factorisation of a complete graph is an isomorphic factorisation where there exists a group G which permutes the factors transitively, and a normal subgroup M of G such that each factor is M-vertex-transitive. If M also acts edge-transitively on each factor, then a homogeneous factorisation of Kn is called an edge-transitive homogeneous factorisation. The aim of this thesis is to study edge-transitive homogeneous factorisations of Kn. We achieve a nearly complete explicit classification except for the case where G is an affine 2-homogeneous group of the form ZR p x G0, where G0 is less than or equal to ΓL(1,p to the power of R). In this case, we obtain necessary and sufficient arithmetic conditions on certain parameters for such factorisations to exist, and give a generic construction that specifies the homogeneous factorisation completely, given that the conditions on the parameters hold. Moreover, we give two constructions of infinite families of examples where we specify the parameters explicitly. In the second infinite family, the arc-transitive factors are generalisations of certain arc-transitive, self-complementary graphs constructed by Peisert in 2001.
30
Janes, Denys Zachary Alexander. "Dynamics of simultaneous epidemics on complex graphs." Thesis, University of Edinburgh, 2017. http://hdl.handle.net/1842/28854.
Texto completo da fonteResumo:
The subject of this thesis is the study of a system of multiple simultaneously spreading diseases, or strains of diseases, in a structured host population. The disease spread is modelled using the well-studied SEIR compartmental model; host population structure is imposed through the use of random graphs, in which each host individual is explicitly connected to a predetermined set of other individuals. Two different graph structures are used: Zipf power-law distributed graphs, in which individuals vary greatly in their number of contacts; and Poisson distributed graphs, in which there is very little variation in the number of contacts. Three separate explorations are undertaken. In the first, the extent to which two SEIR processes will overlap due to chance is examined in the case where they do not affect each other's ability to spread. The overlap is found to increase with increased heterogeneity in the number of contacts, all things equal. Introducing differences in infection probability or a delay between introducing the two strains produces more complex dynamics. I then extend the model to allow strains to modify each other's transmissibility. This is found to lead to modest changes in the size of the outbreak of affected strains, and larger effects on the size of the overlap. The extent of the effect is found to depend strongly on the order in which the strains are introduced to the population. Zipf graphs experience somewhat larger reductions in outbreak size and less reduction of overlap size, but overall the two graphs experience similar effects. This is due to the reduced effect of modification in key high-degree vertices in the Zipf graph being offset by higher local clustering. Finally, I introduce recombination and competition by replacement into the model from the first project. The number of recombinant strains that arise is found to be either very low or very high, with chance governing which occurs. Recombinant strains in Zipf distributed graphs have a significant chance of failing to spread, but not in Poisson distributed graphs. Replacement competition in the presence of a growing number of strains is found to both increase the chance of a strain failing to spread, and to reduce the overall size of outbreaks. This effect is equal in both graph types.
31
Omnès, Thierry J.-F. "Acropolis : un précompilateur de spécification pour l'exploration du transfert et du stockage des données en conception de systèmes embarqués à Haut Débit." Paris, ENMP, 2001. http://www.theses.fr/2001ENMP0995.
Texto completo da fonte
32
Sörensen, Kristina. "Clustering in Financial Markets : A Network Theory Approach." Thesis, KTH, Optimeringslära och systemteori, 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-150577.
Texto completo da fonteResumo:
In this thesis we consider graph partition of a particular kind of complex networks referred to as power law graphs. In particular, we focus our analysis on the market graph, constructed from time series of price return on the American stock market. Two different methods originating from clustering analysis in social networks and image segmentation are applied to obtain graph partitions and the results are evaluated in terms of the structure and quality of the partition. Along with the market graph, power law graphs from three different theoretical graph models are considered. This study highlights topological features common in many power law graphs as well as their differences and limitations. Our results show that the market graph possess a clear clustered structure only for higher correlation thresholds. By studying the internal structure of the graph clusters we found that they could serve as an alternative to traditional sector classification of the market. Finally, partitions for different time series was considered to study the dynamics and stability in the partition structure. Even though the results from this part were not conclusive we think this could be an interesting topic for future research.<br>I denna uppsats studeras graf partition av en typ av komplexa nätverk som kallas power law grafer. Specifikt fokuserar vi på marknadengrafen, konstruerad av tidsserier av aktiepriser på den amerikanska aktiemarknaden. Två olika metoder, initialt utvecklade för klusteranalys i sociala nätverk samt för bildanalys appliceras för att få graf-partitioner och resultaten utvärderas utifrån strukturen och kvaliten på partitionen. Utöver marknadsgrafen studeras aven power law grafer från tre olika teoretiska grafmodeller. Denna studie belyser topologiska egenskaper vanligt förekommande i många power law grafer samt modellerns olikheter och begränsningar. Våra resultat visar att marknadsgrafen endast uppvisar en tydlig klustrad struktur för högre korrelation-trösklar. Genom att studera den interna strukturen hos varje kluster fann vi att kluster kan vara ett alternativ till traditionell marknadsindelning med industriella sektorer. Slutligen studerades partitioner för olika tidsserier för att undersöka dynamiken och stabiliteten i partitionsstrukturen. Trots att resultaten från denna del inte var entydiga tror vi att detta kan vara ett intressant spår för framtida studier.
33
Simmonds, William Francis. "Complete parameterized presentations and almost convex Cayley graphs." Thesis, University of Warwick, 1991. http://wrap.warwick.ac.uk/109313/.
Texto completo da fonteResumo:
This thesis is meant as a contribution to the theory of three classes of groups, those classes being the groups defined by complete parameterized presentations, automatic groups, and groups with almost convex Cayley graphs. Chapter 1 is basically definitions and terminology. Chapter 2 is a short exposition of the theory of automatic groups; we prove only one major result in this chapter (due to (CHEPT)), i.e., that the abelian groups are automatic. In chapter 3 we study presentations of groups and monoids which are complete (with respect to certain orderings of the words in their generators). Such presentations define monoids with fast solutions to their word problems. We define a class of (possibly infinite) presentations which we call r-porameterized, or of type Pr; these presentations are the central theme of this thesis. With the help of the computer program described in chapter 4, we demonstrate that there are group presentations which have infinite r-parameterized completions (i.e. complete supersets), but which have no finite completion with respect to any ShortLex ordering. The 1-parameterized presentations are, arguably, the simplest non finite presentations we can define (at least as far as groups are concerned), but we prove that completeness of such presentations is not in general decidable. Chapter 4 is the description of a (short) program which attempts to complete 1-parameterized group presentations by the Knuth-Bendix method. We conclude the chapter with a short report on its implementation. In chapter 5 we study groups with almost convex Cayley graphs. Such graphs are recursive, but the property of being almost convex does tend to be hard to prove or disprove in practice. We prove that the word length preserving complete groups and the least length bounded automatic groups have almost convex Cayley graphs. We believe that these are strict subclasses because (we shall prove) the group U(3,Z) is almost convex, but is already known not to be automatic and, we conjecture, it has no r-parameterized complete (ShortLex) presentation. We conclude chapter 5 with a slightly generalized, arguably simpler, algebraic proof of J.W. Cannon's theorem that the abelian by finite groups are almost convex.
34
Marchi, M. "RUMIN'S COMPLEX AND INTRINSIC GRAPHS IN CARNOT GROUPS." Doctoral thesis, Università degli Studi di Milano, 2014. http://hdl.handle.net/2434/246343.
Texto completo da fonteResumo:
This thesis is concerned with some aspects of geometric analysis on Carnot groups. In the first chapter, we study differential forms and Rumin's complex on Carnot groups.
In particular, we undertake the analysis of Rumin's Laplacian $\Delta_R$ on the Heisenberg group. We obtain a decomposition of the space of Rumin's forms with $L^2$ coefficients into invariant subspaces and describe the action of $\Delta_R$ restricted to these subspaces up to unitary equivalence. We also obtain that this decomposition provide a $L^p$ decomposition of the space of Rumin's forms.
In the second chapter, we study intrinsic Lipschitz graphs and intrinsic differentiable graphs within Carnot groups. Both seem to be the natural analogues inside Carnot groups of the corresponding Euclidean notions. In particular, we prove that one codimensional intrinsic Lipschitz graphs are sets with locally finite $\G$-perimeter. From this a Rademacher's type theorem for one codimensional graphs in a general class of groups is proved.
35
Armulik, Villem-Adolf. "Ramsey Numbers and Two-colorings ofComplete Graphs." Thesis, Linnéuniversitetet, Institutionen för matematik (MA), 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:lnu:diva-44610.
Texto completo da fonteResumo:
Ramsey theory has to do with order within disorder. This thesis studies two Ramsey numbers, R(3; 3) and R(3; 4), to see if they can provide insight into finding larger Ramsey numbers. The numbers are studied with the help of computer programs. In the second part of the thesis we try to create a coloring of K45 which lacks monochromatic K5 and where each vertex has an equal degree for both color of edges. The results from studying R(3; 3) and R(3; 4) fail to give any further insight into larger Ramsey numbers. Every coloring of K45 we produce contains a monochromatic K5.
36
Liu, Zifan. "Complex systems and health systems, computational challenges." Thesis, Versailles-St Quentin en Yvelines, 2015. http://www.theses.fr/2015VERS001V/document.
Texto completo da fonteResumo:
Le calcul des valeurs propres intervient dans des modèles de maladies d’épidémiques et pourrait être utilisé comme un allié des campagnes de vac- cination dans les actions menées par les organisations de soins de santé. La modélisation épidémique peut être considérée, par analogie, comme celle des viruses d’ordinateur qui dépendent de l’état de graphe sous-jacent à un moment donné. Nous utilisons PageRank comme méthode pour étudier la propagation de l’épidémie et d’envisager son calcul dans le cadre de phé- nomène petit-monde. Une mise en œuvre parallèle de méthode multiple de "implicitly restar- ted Arnoldi method" (MIRAM) est proposé pour calculer le vecteur propre dominant de matrices stochastiques issus de très grands réseaux réels. La grande valeur de "damping factor" pour ce problème fait de nombreux algo- rithmes existants moins efficace, tandis que MIRAM pourrait être promet- teuse. Nous proposons également dans cette thèse un générateur de graphe parallèle qui peut être utilisé pour générer des réseaux synthétisés distri- bués qui présentent des structures "scale-free" et petit-monde. Ce générateur pourrait servir de donnée pour d’autres algorithmes de graphes également. MIRAM est mis en œuvre dans le cadre de trilinos, en ciblant les grandes données et matrices creuses représentant des réseaux sans échelle, aussi connu comme les réseaux de loi de puissance. Hypergraphe approche de partitionnement est utilisé pour minimiser le temps de communication. L’al- gorithme est testé sur un grille national de Grid5000. Les expériences sur les très grands réseaux tels que Twitter et Yahoo avec plus de 1 milliard de nœuds sont exécutées. Avec notre mise en œuvre parallèle, une accélération de 27× est satisfaite par rapport au solveur séquentiel<br>The eigenvalue equation intervenes in models of infectious disease prop- agation and could be used as an ally of vaccination campaigns in the ac- tions carried out by health care organizations. The epidemiological model- ing techniques can be considered by analogy, as computer viral propagation which depends on the underlying graph status at a given time. We point out PageRank as method to study the epidemic spread and consider its calcula- tion in the context of small-world phenomenon. A parallel implementation of multiple implicitly restarted Arnoldi method (MIRAM) is proposed for calculating dominant eigenpair of stochastic matrices derived from very large real networks. Their high damp- ing factor makes many existing algorithms less efficient, while MIRAM could be promising. We also propose in this thesis a parallel graph gen- erator that can be used to generate distributed synthesized networks that display scale-free and small-world structures. This generator could serve as a testbed for graph related algorithms. MIRAM is implemented within the framework of Trilinos, targeting big data and sparse matrices representing scale-free networks, also known as power law networks. Hypergraph partitioning approach is employed to minimize the communication overhead. The algorithm is tested on a nation wide cluster of clusters Grid5000. Experiments on very large networks such as twitter and yahoo with over 1 billion nodes are conducted. With our parallel implementation, a speedup of 27× is met compared to the sequential solver
37
Dodo, Meva. "Etude de l'apport de la visualisation 3D interactive pour l'administration de systèmes complexe." Toulouse 3, 2008. http://thesesups.ups-tlse.fr/358/.
Texto completo da fonteResumo:
Cette thèse propose de nouvelles méthodes qui permettent de faciliter l'analyse et la compréhension de la structure des systèmes complexes ainsi que les différents événements générés par les ressources. Des techniques de représentation 3D sont proposées afin de permettre la visualisation de tout type de structure de systèmes complexes. Notre approche est matérialisée par un nouvel algorithme d'affichage 3D de larges graphes. Cette algorithme est basé sur une nouvelle approche d'optimisation de l'algorithme force-attraction-répulsion (FDP) afin mieux de distribuer les nœuds d'un graphe dans un espace 3D, et nous l'avons associé à des méthodes d'optimisation afin d'améliorer sa performance. La deuxième approche se propose d'associer à la représentation 3D du graphe des mondes 3D qui facilitent l'analyse et l'exploration de la structure du système à étudier<br>The aim of this thesis is to study new methods which allow to improve the understanding of complex systems' structure and to analyze the various events generated by its resources. Three-dimensional techniques are proposed to easy the analysis of the structure of complex systems. A new algorithm for drawing, in 3D, large graphs is proposed in order to optimize the layout of a complex structure. Our method is based on the optimization of the force-directed placement algorithm (FDP) that allows effectively and aesthetically displaying large graphs. Our second approach is to propose metaphors that allow to easily understand the different events generated by devices. This approach is based on the three attributes that define an event: "what, when, where", and it is associated with filtering techniques that choose interesting events according to the management needs
38
Couturier, Jean-François. "Algorithmes exacts et exponentiels sur les graphes : énumération, comptage et optimisation." Electronic Thesis or Diss., Université de Lorraine, 2012. http://www.theses.fr/2012LORR0325.
Texto completo da fonteResumo:
L'hypothèse qu'un grand nombre de problèmes n'admettent pas d'algorithme (exact et déterministe) polynomial date de l'avènement de la théorie de la NP-complétude dans les années 70. Depuis, de nombreuses théories et techniques algorithmiques se sont développées pour résoudre ces problèmes difficiles le plus efficacement possible. Dans cette thèse, nous nous intéressons aux algorithmes exacts faiblement exponentiels. L'objectif est d'obtenir des algorithmes de complexité 0* (c^n) où n est la taille de la donnée et c une Constante la plus faible possible<br>The assumption that many problems do not admit algorithm (exact and deterministic) polynomial ate of the advent of the theory of NP-completeness in the 70s. Since many theories and algorithmic techniques have been developed to solve these problems difficult as efficiently as possible. In this thesis, we focus on exact algorithms weakly exponential. The objective is to obtain algorithms complexity 0 * (c ^ n) where n is the size of the data and one constant c as small as possible
39
Madduri, Kamesh. "A high-performance framework for analyzing massive complex networks." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/24712.
Texto completo da fonteResumo:
Thesis (Ph.D.)--Computing, Georgia Institute of Technology, 2009.<br>Committee Chair: Bader, David; Committee Member: Berry, Jonathan; Committee Member: Fujimoto, Richard; Committee Member: Saini, Subhash; Committee Member: Vuduc, Richard
40
Kosebinu, Kazeem A. "Partially Oriented 6-star Decomposition of Some Complete Mixed Graphs." Digital Commons @ East Tennessee State University, 2021. https://dc.etsu.edu/etd/3943.
Texto completo da fonteResumo:
Let $M_v$ denotes a complete mixed graph on $v$ vertices, and let $S_6^i$ denotes the partial orientation of the 6-star with twice as many arcs as edges. In this work, we state and prove the necessary and sufficient conditions for the existence of $\lambda$-fold decomposition of a complete mixed graph into $S_6^i$ for $i\in\{1,2,3,4\}$. We used the difference method for our proof in some cases. We also give some general sufficient conditions for the existence of $S_6^i$-decomposition of the complete bipartite mixed graph for $i\in\{1,2,3,4\}$. Finally, this work introduces the decomposition of a complete mixed graph with a hole into mixed stars.
41
Watts, Valerie Lynn. "Covers and partitions of graphs by complete bipartite subgraphs." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2001. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp05/NQ63469.pdf.
Texto completo da fonte
42
Anzur, Matthew Paul. "k-star decomposition of lambda-fold complete multipartite graphs." Auburn, Ala., 2007. http://repo.lib.auburn.edu/07M%20Dissertations/ANZUR_MATTHEW_39.pdf.
Texto completo da fonte
43
King, Andrew James Howell. "On decomposition of complete infinite graphs into spanning trees." Thesis, University of Reading, 1990. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.253454.
Texto completo da fonte
44
Appelt, Eric Andrew. "On the Bandwidth of a Product of Complete Graphs." Miami University / OhioLINK, 2003. http://rave.ohiolink.edu/etdc/view?acc_num=miami1043425640.
Texto completo da fonte
45
Dubey, Mohnish [Verfasser]. "Towards Complex Question Answering over Knowledge Graphs / Mohnish Dubey." Bonn : Universitäts- und Landesbibliothek Bonn, 2021. http://d-nb.info/1238687849/34.
Texto completo da fonte
46
Diot, Emilie. "Etude structurelle et algorithmique des graphes pouvant être séparés avec des plus courts chemins." Thesis, Bordeaux 1, 2011. http://www.theses.fr/2011BOR14425/document.
Texto completo da fonteResumo:
Les graphes sont des objets couramment utilisés pour modéliser de nombreuses situations réelles comme des réseaux routiers, informatiques ou encore électriques. Ils permettent de résoudre des problèmes sur ces réseaux comme le routage (aller d'un sommet à un autre en suivant les arêtes du graphe) ou encore leur exploration (obtenir une carte du graphe étudié). Les réseaux étudiés, et donc les graphes qui les modélisent, peuvent être grands, c'est-à-dire avoir un très grand nombre de sommets. Dans ce cas, comme dans le cas de l'étude de grandes données en général, nous pouvons utiliser le paradigme << Diviser pour mieux régner >> pour répondre aux questions posées. En effet, en travaillant sur des petites parties du graphe et en fusionnant les résultats obtenus sur ces petites parties, on peut obtenir le résultat sur le graphe global. Dans ce document, nous présenterons une manière de décomposer les graphes en utilisant des plus courts chemins comme séparateurs. Cette décomposition permet d'obtenir, par exemple, un routage efficace, un étiquetage compacte pour pouvoir estimer les distances entre les sommets d'un graphe ou encore une navigation efficace dans les graphes<< petit monde >>. Cette méthode va nous permettre de définir de nouvelles classes de graphes<br>Graphs are widely used to MODELISER a lot of real situations like road networks, computers networks or electricity ones. Using them, we can solve problems on these networks like routing (go from a vertex ti another one) or explore them (to have a map of studied graph).Studied networks, and so graphs which MODELISER them, can be large (i.e. have a lot of vertices). In this case, we can use the paradigm "Divide and conquer" to answer the questions. Indeed, working on small parts of graphs and merging the results on these small parts, we can obtain the result on the whole graph.In this document, we present a way to separate graphs using shortest paths like separators. This decomposition let to obtain a compact routing, a compact labeling to estimate the distance between vertices of the graph. This method let us to define new class of graphs
47
Parikh, Nidhi Kiranbhai. "Generating Random Graphs with Tunable Clustering Coefficient." Thesis, Virginia Tech, 2011. http://hdl.handle.net/10919/31591.
Texto completo da fonteResumo:
Most real-world networks exhibit a high clustering coefficientâ the probability that two neighbors
of a node are also neighbors of each other. We propose four algorithms CONF-1, CONF-2,
THROW-1, and THROW-2 which are based on the configuration model and that take triangle degree
sequence (representing the number of triangles/corners at a node) and single-edge degree sequence
(representing the number of single-edges/stubs at a node) as input and generate a random graph
with a tunable clustering coefficient. We analyze them theoretically and empirically for the case of
a regular graph. CONF-1 and CONF-2 generate a random graph with the degree sequence and the
clustering coefficient anticipated from the input triangle and single-edge degree sequences. At each
time step, CONF-1 chooses each node for creating triangles or single edges with the same probability,
while CONF-2 chooses a node for creating triangles or single edge with a probability proportional
to their number of unconnected corners or unconnected stubs, respectively. Experimental results
match quite well with the anticipated clustering coefficient except for highly dense graphs, in which
case the experimental clustering coefficient is higher than the anticipated value. THROW-2 chooses
three distinct nodes for creating triangles and two distinct nodes for creating single edges, while
they need not be distinct for THROW-1. For THROW-1 and THROW-2, the degree sequence and the
clustering coefficient of the generated graph varies from the input. However, the expected degree
distribution, and the clustering coefficient of the generated graph can also be predicted using analytical
results. Experiments show that, for THROW-1 and THROW-2, the results match quite well with
the analytical results. Typically, only information about degree sequence or degree distribution is
available. We also propose an algorithm DEG that takes degree sequence and clustering coefficient
as input and generates a graph with the same properties. Experiments show results for DEG that
are quite similar to those for CONF-1 and CONF-2.<br>Master of Science
48
Santos, Emerson Soares dos. "Aspectos geográficos e epidemiológicos da hanseníase em Cuiabá e Várzea Grande - MT." Universidade de São Paulo, 2012. http://www.teses.usp.br/teses/disponiveis/8/8135/tde-28082012-123829/.
Texto completo da fonteResumo:
A hanseníase é um importante problema de saúde pública nas cidades de Cuiabá e Várzea Grande. O coeficiente de detecção para as duas cidades, em 2010, era de 6,97 casos por 10.000 habitantes, o que caracteriza a forte presença endêmica da doença nesta área. A hipótese é de que os casos de hanseníase estariam agrupados, formando focos de contato e disseminação relacionados ao ambiente geográfico e fatores sociais e econômicos. Com isso, se objetiva analisar a distribuição espacial e os aspectos epidemiológicos da doença sob a perspectiva da Geografia. Trata-se de um estudo ecológico, tanto do ponto de vista da metodologia proposta por Maximilien Sorre quanto pelo seu delineamento epidemiológico, utilizando técnicas baseadas em Análise Espacial de Dados Geográficos e Análise Multivariada de Dados. Foram georreferenciados os casos de hanseníase registrados em Cuiabá e Várzea Grande entre os anos de 1999 a 2010, e posteriormente submetidos a testes estatísticos de dependência espacial entre casos, de existência de focos espaciais e de áreas de risco, e da possível influência de fatores sócio-econômicos e ambientais na presença ou ausência deste risco. Os resultados indicam a formação de focos endêmicos durante o período do estudo, cuja distribuição está condicionada a fatores sócio-econômicos e às formas de uso-ocupação da terra no ambiente urbano, mas esses fatores têm graus de influência diferentes dependendo da escala de análise. Na escala do bairro, o risco relativo esteve relacionado com a existência de domicílios com muitos moradores em áreas com média a alta densidade de casas, baixos percentuais de cobertura de saneamento básico e baixa renda. Nesta escala, o saneamento básico é o principal fator com maior poder de explicação entre as variáveis estudadas, e já na escala do setor censitário, não é um fator com grande poder explicativo e sem significância estatística, tendo na alfabetização e uso da terra os principais fatores explicativos.<br>The Hansens disease is an important public health problem in the cities of Cuiabá and Várzea Grande. The detection rate for the two cities in 2010 was 6.97 cases per 10,000 inhabitants, which characterizes the strong presence of endemic disease in this area. The hypothesis is that Hansens disease cases were grouped together, forming foci of contact and dissemination related to the geographical environment and social and economic factors. Therefore, the objective of this study is to analyze the spatial distribution and epidemiological aspects of the disease from the perspective of the Geography. It is an ecological study, both from the standpoint of the methodology proposed by Maximilien Sorre as for its epidemiological design. The techniques used are based on Spatial Data Analysis and Multivariate Data Analysis. The Hansens disease cases registered in Cuiabá and Várzea Grande from 1999 to 2010 were geocoded, then submitted to statistical tests for spatial dependence among cases, existence of spatial foci and risk areas, and the possible influence of socio-economic and environmental factors in the presence or absence this risk. The results indicate the formation of endemic foci during the period of study, and the distribution is conditioned by socio-economic factors and forms of land-use in the urban area, however these factors have different grades of influence depending on the scale of analysis. In neighborhood scale relative risk was related to the existence of houses with many residents in areas with medium to high density of houses, low coverage of basic sanitary services and low income. In this scale, basic sanitary services is a major factor with the greatest explanatory potential between the studied variables, however in the census tract scale, it is not a factor with great explanatory potential and it is not statistically significant, being the literacy and land use, the principal factors of explanation.
49
Pogorelcnik, Romain. "Decomposition by complete minimum separators and applications." Thesis, Clermont-Ferrand 2, 2012. http://www.theses.fr/2012CLF22301/document.
Texto completo da fonteResumo:
Nous avons utilisé la décomposition par séparateurs minimaux complets. Pour décomposer un graphe G, il est nécessaire de trouver les séparateurs minimaux dans le graphe triangulé H correspondant. Dans ce contexte, nos premiers efforts se sont tournés vers la détection de séparateurs minimaux dans un graphe triangulé. Nous avons défini une structure, que nous avons nommée 'atom tree'. Cette dernière est inspirée du 'clique tree' et permet d'obtenir et de représenter les atomes qui sont les produits de la décomposition. Lors de la manipulation de données à l'aide de treillis de Galois, nous avons remarqué que la décomposition par séparateurs minimaux permettait une approche de type `Diviser pour régner' pour les treillis de Galois. La détection des gènes fusionnés, qui est une étape importante pour la compréhension de l'évolution des espèces, nous a permis d'appliquer nos algorithmes de détection de séparateurs minimaux complets, qui nous a permis de détecter et regrouper de manière efficace les gènes fusionnés. Une autre application biologique fut la détection de familles de gènes d'intérêts à partir de données de niveaux d'expression de gènes. La structure de `l'atom tree' nous a permis d'avoir un bon outils de visualisation et de gérer des volumes de données importantes<br>We worked on clique minimal separator decomposition. In order to compute this decomposition on a graph G we need to compute the minimal separators of its triangulation H. In this context, the first efforts were on finding a clique minimal separators in a chordal graph. We defined a structure called atom tree inspired from the clique tree to compute and represent the final products of the decomposition, called atoms. The purpose of this thesis was to apply this technique on biological data. While we were manipulating this data using Galois lattices, we noticed that the clique minimal separator decomposition allows a divide and conquer approach on Galois lattices. One biological application of this thesis was the detection of fused genes which are important evolutionary events. Using algorithms we produced in the course of along our work we implemented a program called MosaicFinder that allows an efficient detection of this fusion event and their pooling. Another biological application was the extraction of genes of interest using expression level data. The atom tree structure allowed us to have a good visualization of the data and to be able to compute large datasets
50
Friggeri, Adrien. "A Quantitative Theory of Social Cohesion." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2012. http://tel.archives-ouvertes.fr/tel-00737199.
Texto completo da fonteResumo:
Community, a notion transversal to all areas of Social Network Analysis, has drawn tremendous amount of attention across the sciences in the past decades. Numerous attempts to characterize both the sociological embodiment of the concept as well as its observable structural manifestation in the social network have to this date only converged in spirit. No formal consensus has been reached on the quantifiable aspects of community, despite it being deeply linked to topological and dynamic aspects of the underlying social network. Presenting a fresh approach to the evaluation of communities, this thesis introduces and builds upon the cohesion, a novel metric which captures the intrinsic quality, as a community, of a set of nodes in a network. The cohesion, defined in terms of social triads, was found to be highly correlated to the subjective perception of communitiness through the use of a large-scale online experiment in which users were able to compute and rate the quality of their social groups on Facebook. Adequately reflecting the complexity of social interactions, the problem of finding a maximally cohesive group inside a given social network is shown to be NP-hard. Using a heuristic approximation algorithm, applications of the cohesion to broadly different use cases are highlighted, ranging from its application to network visualization, to the study of the evolution of agreement groups in the United States Senate, to the understanding of the intertwinement between subjects' psychological traits and the cohesive structures in their social neighborhood. The use of the cohesion proves invaluable in that it offers non-trivial insights on the network structure and its relation to the associated semantic.