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.
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 fonteDomination 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
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 fonteSima, 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 fonteKnowledge 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
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 fonteOn étudie certaines propriétés algorithmiques et combinatoires pour successivement trois types de colorations : orientée, mixte et décomposition acircuitique.
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.
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 fonteThe 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
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 fonteThe 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
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 fonteWe 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
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 fonteMany 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
Dieng, Youssou. "Décomposition arborescente des graphes planaires et routage compact". Thesis, Bordeaux 1, 2009. http://www.theses.fr/2009BOR13855/document.
Texto completo da fonteIn 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
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 fonteSehgal, 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 fonteRocha, 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 fonteOnyumbe, 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 fonteUduman, 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 fonteTremblay, 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 fonteThis 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
Knopp, Sebastian. "Complex Job-Shop Scheduling with Batching in Semiconductor Manufacturing". Thesis, Lyon, 2016. http://www.theses.fr/2016LYSEM014/document.
Texto completo da fonteThe 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
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 fonteBoudermine, 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 fonteNowadays, 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
Schickinger, Thomas. "Complete subgraphs of random graphs". [S.l. : s.n.], 2002. http://deposit.ddb.de/cgi-bin/dokserv?idn=966629353.
Texto completo da fonteKumwenda, 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 fonteWassmer, Arnold. "A dual independence complex". [S.l.] : [s.n.], 2005. http://deposit.ddb.de/cgi-bin/dokserv?idn=976684314.
Texto completo da fonteHamon, 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 fonteBike-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
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 fonteThis 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
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 fonteGillani, 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 fonteThere 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
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 fonteCouturier, 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 fonteThe 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
Pan, Shengjun. "On the Crossing Numbers of Complete Graphs". Thesis, University of Waterloo, 2006. http://hdl.handle.net/10012/1174.
Texto completo da fonteLim, 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 fonteJanes, Denys Zachary Alexander. "Dynamics of simultaneous epidemics on complex graphs". Thesis, University of Edinburgh, 2017. http://hdl.handle.net/1842/28854.
Texto completo da fonteOmnè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 fonteSö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 fonteI 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.
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 fonteMarchi, 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 fonteArmulik, 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 fonteLiu, Zifan. "Complex systems and health systems, computational challenges". Thesis, Versailles-St Quentin en Yvelines, 2015. http://www.theses.fr/2015VERS001V/document.
Texto completo da fonteThe 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
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 fonteThe 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
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 fonteThe 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
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 fonteCommittee Chair: Bader, David; Committee Member: Berry, Jonathan; Committee Member: Fujimoto, Richard; Committee Member: Saini, Subhash; Committee Member: Vuduc, Richard
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 fonteWatts, 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 fonteAnzur, 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 fonteKing, 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 fonteAppelt, 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 fonteDubey, 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 fonteDiot, 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 fonteGraphs 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
Parikh, Nidhi Kiranbhai. "Generating Random Graphs with Tunable Clustering Coefficient". Thesis, Virginia Tech, 2011. http://hdl.handle.net/10919/31591.
Texto completo da fonteMaster of Science
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 fonteThe 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.
Pogorelcnik, Romain. "Decomposition by complete minimum separators and applications". Thesis, Clermont-Ferrand 2, 2012. http://www.theses.fr/2012CLF22301/document.
Texto completo da fonteWe 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
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 fonte