To see the other types of publications on this topic, follow the link: Graph isomorphism.
Dissertations / Theses on the topic 'Graph isomorphism'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Graph isomorphism.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Nabti, Chems Eddine. "Subgraph Isomorphism Search In Massive Graph Data." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSE1293/document.
Full textAbstract:
L'interrogation de graphes de données est un problème fondamental qui connait un grand intérêt, en particulier pour les données structurées massives où les graphes constituent une alternative prometteuse aux bases de données relationnelles pour la modélisation des grandes masses de données. Cependant, l'interrogation des graphes de données est différente et plus complexe que l'interrogation des données relationnelles à base de tables. La tâche principale impliquée dans l'interrogation de graphes de données est la recherche d'isomorphisme de sous-graphes qui est un problème NP-complet.La recherche d'isomorphisme de sous-graphes est un problème très important impliqué dans divers domaines comme la reconnaissance de formes, l'analyse des réseaux sociaux, la biologie, etc. Il consiste à énumérer les sous-graphes d'un graphe de données qui correspondent à un graphe requête. Les solutions les plus connues de ce problème sont basées sur le retour arrière (backtracking). Elles explorent un grand espace de recherche, ce qui entraîne un coût de traitement élevé, notamment dans le cas de données massives.Pour réduire le temps et la complexité en espace mémoire dans la recherche d'isomorphisme de sous-graphes, nous proposons d'utiliser des graphes compressés. Dans notre approche, la recherche d'isomorphisme de sous-graphes est réalisée sur une représentation compressée des graphes sans les décompresser. La compression des graphes s'effectue en regroupant les sommets en super-sommets. Ce concept est connu dans la théorie des graphes par la décomposition modulaire. Il sert à générer une représentation en arbre d'un graphe qui met en évidence des groupes de sommets qui ont les mêmes voisins. Avec cette compression, nous obtenons une réduction substantielle de l'espace de recherche et par conséquent, une économie significative dans le temps de traitement.Nous proposons également une nouvelle représentation des sommets du graphe, qui simplifie le filtrage de l'espace de recherche. Ce nouveau mécanisme appelé compact neighborhood Index (CNI) encode l'information de voisinage autour d'un sommet en un seul entier. Cet encodage du voisinage réduit la complexité du temps de filtrage de cubique à quadratique. Ce qui est considérable pour les données massifs.Nous proposons également un algorithme de filtrage itératif qui repose sur les caractéristiques des CNIs pour assurer un élagage global de l'espace de recherche.Nous avons évalué nos approches sur plusieurs datasets et nous les avons comparées avec les algorithmes de l’état de l’artQuerying graph data is a fundamental problem that witnesses an increasing interest especially for massive structured data where graphs come as a promising alternative to relational databases for big data modeling. However, querying graph data is different and more complex than querying relational table-based data. The main task involved in querying graph data is subgraph isomorphism search which is an NP-complete problem. Subgraph isomorphism search, is an important problem which is involved in various domains such as pattern recognition, social network analysis, biology, etc. It consists to enumerate the subgraphs of a data graph that match a query graph. The most known solutions of this problem are backtracking-based. They explore a large search space which results in a high computational cost when we deal with massive graph data. To reduce time and memory space complexity of subgraph isomorphism search. We propose to use compressed graphs. In our approach, subgraph isomorphism search is achieved on compressed representations of graphs without decompressing them. Graph compression is performed by grouping vertices into super vertices. This concept is known, in graph theory, as modular decomposition. It is used to generate a tree representation of a graph that highlights groups of vertices that have the same neighbors. With this compression we obtain a substantial reduction of the search space and consequently a significant saving in the processing time. We also propose a novel encoding of vertices that simplifies the filtering of the search space. This new mechanism is called compact neighborhood Index (CNI). A CNI distills all the information around a vertex in a single integer. This simple neighborhood encoding reduces the time complexity of vertex filtering from cubic to quadratic which is considerable for big graphs. We propose also an iterative local global filtering algorithm that relies on the characteristics of CNIs to ensure a global pruning of the search space.We evaluated our approaches on several real-word datasets and compared them with the state of the art algorithms
2
Beckman, David Eugene Preskill John P. "Investigations in quantum computing: causality and graph isomorphism /." Diss., Pasadena, Calif. : California Institute of Technology, 2004. http://resolver.caltech.edu/CaltechETD:etd-05272004-174253.
Full text
3
Kuhnert, Sebastian. "Space efficient algorithms for graph isomorphism and representation." Doctoral thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät, 2016. http://dx.doi.org/10.18452/17447.
Full textAbstract:
Beim Graphisomorphieproblem geht es um die Frage, ob zwei Graphen bis auf Knotenumbenennungen die gleiche Struktur haben. Es ist eines der wenigen verbleibenden natürlichen Probleme, für die weder ein Polynomialzeitalgorithmus noch NP-Härte bekannt ist. Aus dieser Situation ist ein Forschungszweig erwachsen, der effiziente Isomorphiealgorithmen für eingeschränkte Graphklassen entwickelt. Der Hauptbeitrag dieser Arbeit besteht in Logspace-Algorithmen, die das Isomorphieproblem für k-Bäume, Intervallgraphen, sowie Helly- und Proper-Kreisbogengraphen lösen. Dies verbessert zuvor bekannte parallele Algorithmen und führt zu einer vollständigen Klassifikation der Komplexität dieser Probleme, da für sie auch Logspace-Härte nachgewiesen wird. Tatsächlich leisten die vorgestellten Algorithmen mehr: Im Fall der k-Bäume berechnet der Algorithmus kanonische Knotenbenennungen mit O(k log n) Platz. Eine alternative Implementation des Algorithmus kommt mit O((k+1)!n) Zeit aus – hierbei ist n die Anzahl der Knoten – und ist damit der schnellste bekannte FPT-Algorithmus für Isomorphie von k-Bäumen. Die Algorithmen für Intervall- und Kreisbogengraphen berechnen kanonische Repräsentationen – das heißt, sie weisen jedem Knoten ein Intervall (beziehungsweise einen Kreisbogen) zu, sodass diese sich genau dann schneiden, wenn die zugehörigen Knoten benachbart sind, und isomorphe Eingabegraphen das gleiche Intervallmodell (beziehungsweise Kreisbogenmodell) erhalten. Außerdem werden auch Logspace-Algorithmen angegeben, die Intervallrepräsentationen mit zusätzlichen Eigenschaften berechnen – oder erkennen, dass dies nicht möglich ist: Für die resultierenden Intervallmodelle kann gefordert werden, dass sie proper sind (also kein Intervall ein anderes enthält), dass sie unit sind (also alle Intervalle die gleiche Länge haben) oder dass die Längen der paarweisen Schnitte (und optional der einzelnen Intervalle) vorgegebenen Werten entsprechen.The graph isomorphism problem deals with the question if two graphs have the same structure up to renaming their vertices. It is one of the few remaining natural problems for which neither a polynomial-time algorithm nor NP-hardness is known. This situation has led to a branch of research that develops efficient algorithms for special cases of the graph isomorphism problem, where the input graphs are required to be from restricted graph classes. The main contribution of this thesis comprises of logspace algorithms that solve the isomorphism problem for k-trees, interval graphs, Helly circular-arc graphs and proper circular-arc graphs. This improves previously known parallel algorithms and leads to a complete classification of the complexity of these problems, as they are also shown to be hard for logspace. In fact, these algorithms achieve more: In the case of k-trees, the algorithm computes canonical labelings in space O(k log n). An alternative implementation runs in time O((k+1)!n), where n is the number of vertices, yielding the fastest known FPT algorithm for k-tree isomorphism. The algorithms for interval and circular-arc graphs actually compute canonical representations, i.e., each vertex is assigned an interval (or arc) such that these intersect each other if and only if the corresponding vertices are adjacent, and isomorphic input graphs receive the same interval (or arc) model. This thesis also presents logspace algorithms that compute interval representations with additional properties, or detect that this is not possible: The resulting interval models can be required to be proper (no interval contains another), unit (all intervals have the same length), or to satisfy prescribed lengths for pairwise intersections (and possibly prescribed lengths of intervals).
4
Ayeh, Eric Namuduri Kamesh. "An investigation into graph isomorphism based zero-knowledge proofs." [Denton, Tex.] : University of North Texas, 2009. http://digital.library.unt.edu/ark:/67531/metadc12076.
Full text
5
Ayeh, Eric. "An investigation into graph isomorphism based zero-knowledge proofs." Thesis, University of North Texas, 2009. https://digital.library.unt.edu/ark:/67531/metadc12076/.
Full textAbstract:
Zero-knowledge proofs protocols are effective interactive methods to prove a node's identity without disclosing any additional information other than the veracity of the proof. They are implementable in several ways. In this thesis, I investigate the graph isomorphism based zero-knowledge proofs protocol. My experiments and analyses suggest that graph isomorphism can easily be solved for many types of graphs and hence is not an ideal solution for implementing ZKP.
6
Lester, David. "Combinator graph reduction : A congruence and its applications." Thesis, University of Oxford, 1988. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.236057.
Full text
7
Culp, Laura. "An Isomorphism Theorem for Graphs." VCU Scholars Compass, 2009. http://scholarscompass.vcu.edu/etd/1952.
Full textAbstract:
In the 1970’s, L. Lovász proved that two graphs G and H are isomorphic if and only if for every graph X , the number of homomorphisms from X → G equals the number of homomorphisms from X → H . He used this result to deduce cancellation properties of the direct product of graphs. We develop a result analogous to Lovász’s theorem, but in the class of graphs without loops and with weak homomorphisms. We apply it prove a general cancellation property for the strong product of graphs.
8
Meana, Richard William Piper. "Approximate Sub-Graph Isomorphism For Watermarking Finite State Machine Hardware." Scholar Commons, 2013. http://scholarcommons.usf.edu/etd/4728.
Full textAbstract:
We present a method of mitigating theft of sequential circuit Intellectual Property hardware designs through means of watermarking. Hardware watermarking can be performed by selectively embedding a watermark in the state encoding of the Finite State Machine. This form of watermarking can be achieved by matching a directed graph representation of the watermark with a sub-graph in state transition graph representation of the FSM. We experiment with three approaches: a brute force method that provides a proof of concept, a greedy algorithm that provides excellent runtime with a drawback of sub-optimal results, and finally a simulated annealing method that provides near optimal solutions with runtimes that meet our performance goals. The simulated annealing approach when applied on a ten benchmarks chosen from IWLS 93 benchmark suite, provides watermarking results with edge overhead of less than 6% on average with runtimes not exceeding five minutes.
9
Balasubramanian, Suman. "On the Erdős-Sòs conjecture and the Cayley Isomorphism Problem." Diss., Mississippi State : Mississippi State University, 2009. http://library.msstate.edu/etd/show.asp?etd=etd-07102009-113145.
Full text
10
Tener, Greg. "ATTACKS ON DIFFICULT INSTANCES OF GRAPH ISOMORPHISM: SEQUENTIAL AND PARALLEL ALGORITHMS." Doctoral diss., University of Central Florida, 2009. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/2631.
Full textAbstract:
The graph isomorphism problem has received a great deal of attention on both theoretical and practical fronts. However, a polynomial algorithm for the problem has yet to be found. Even so, the best of the existing algorithms perform well in practice; so well that it is challenging to find hard instances for them. The most efficient algorithms, for determining if a pair of graphs are isomorphic, are based on the individualization-refinement paradigm, pioneered by Brendan McKay in 1981 with his algorithm nauty. Nauty and various improved descendants of nauty, such as bliss and saucy, solve the graph isomorphism problem by determining a canonical representative for each of the graphs. The graphs are isomorphic if and only if their canonical representatives are identical. These algorithms also detect the symmetries in a graph which are used to speed up the search for the canonical representative--an approach that performs well in practice. Yet, several families of graphs have been shown to exist which are hard for nauty-like algorithms. This dissertation investigates why these graph families pose difficulty for individualization-refinement algorithms and proposes several techniques for circumventing these limitations. The first technique we propose addresses a fundamental problem pointed out by Miyazaki in 1993. He constructed a family of colored graphs which require exponential time for nauty (and nauty's improved descendants). We analyze Miyazaki's construction to determine the source of difficulty and identify a solution. We modify the base individualization-refinement algorithm by exploiting the symmetries discovered in a graph to guide the search for its canonical representative. This is accomplished with the help of a novel data structure called a guide tree. As a consequence, colored Miyazaki graphs are processed in polynomial time--thus obviating the only known exponential upper-bound on individualization-refinement algorithms (which has stood for the last 16 years). The preceding technique can only help if a graph has enough symmetry to exploit. It cannot be used for another family of hard graphs that have a high degree of regularity, but possess few actual symmetries. To handle these instances, we introduce an adaptive refinement method which utilizes the guide-tree data structure of the preceding technique to use a stronger vertex-invariant, but only when needed. We show that adaptive refinement is very effective, and it can result in dramatic speedups. We then present a third technique ideally suited for large graphs with a preponderance of sparse symmetries. A method was devised by Darga et al. for dealing with these large and highly symmetric graphs, which can reduce runtime by an order of magnitude. We explain the method and show how to incorporate it into our algorithm. Finally, we develop and implement a parallel algorithm for detecting the symmetries in, and finding a canonical representative of a graph. Our novel parallel algorithm divides the search for the symmetries and canonical representative among each processor, allowing for a high degree of scalability. The parallel algorithm is benchmarked on the hardest problem instances, and shown to be effective in subdividing the search space.Ph.D.
School of Electrical Engineering and Computer Science
Engineering and Computer Science
Computer Science PhD
11
Tamburini, Caterina. "The isomorphism problem for directed acyclic graphs: an application to multivector fields." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2018. http://amslaurea.unibo.it/15793/.
Full textAbstract:
This thesis is based on a project developed by a group of researchers at the Faculty of Mathematics and Computer Science at the Jagiellonian University of Krakow. They study sampled dynamics using combinatorial multivector fields. Applying a decomposition into strongly connected components, it is possible to create a directed acyclic graph, called Morse graph, which is a description of the multivector field's global dynamics. Therefore the purpose of this thesis is to compare directed acyclic graphs. In the first chapter we describe the creation process of a Morse graph and an algorithm to study the graph isomorphism problem. The second chapter is dedicated to our personal work, so we describe four Python tests we developed to establish whether two directed acyclic graphs are definitely not isomorphic. In the third chapter we sum up many examples. The last chapter aims to present a possible way for the future work, that is to treat a combinatorial multivector filed as a finite topological space.
12
Dona, Daniele [Verfasser]. "Growth in finite groups and the Graph Isomorphism Problem / Daniele Dona." Göttingen : Niedersächsische Staats- und Universitätsbibliothek Göttingen, 2020. http://d-nb.info/1216330662/34.
Full text
13
Tener, Greg Daniel. "Attacks on difficult instances of graph isomorphism sequential and parallel algorithms /." Orlando, Fla. : University of Central Florida, 2009. http://purl.fcla.edu/fcla/etd/CFE0002894.
Full text
14
Ilchenko, Alexey. "An approach to Graph Isomorphism using Spanning Trees generated by Breadth First Search." Case Western Reserve University School of Graduate Studies / OhioLINK, 2014. http://rave.ohiolink.edu/etdc/view?acc_num=case1405079402.
Full text
15
Tian, Chao. "Towards effective analysis of big graphs : from scalability to quality." Thesis, University of Edinburgh, 2017. http://hdl.handle.net/1842/29578.
Full textAbstract:
This thesis investigates the central issues underlying graph analysis, namely, scalability and quality. We first study the incremental problems for graph queries, which aim to compute the changes to the old query answer, in response to the updates to the input graph. The incremental problem is called bounded if its cost is decided by the sizes of the query and the changes only. No matter how desirable, however, our first results are negative: for common graph queries such as graph traversal, connectivity, keyword search and pattern matching, their incremental problems are unbounded. In light of the negative results, we propose two new characterizations for the effectiveness of incremental computation, and show that the incremental computations above can still be effectively conducted, by either reducing the computations on big graphs to small data, or incrementalizing batch algorithms by minimizing unnecessary recomputation. We next study the problems with regards to improving the quality of the graphs. To uniquely identify entities represented by vertices in a graph, we propose a class of keys that are recursively defined in terms of graph patterns, and are interpreted with subgraph isomorphism. As an application, we study the entity matching problem, which is to find all pairs of entities in a graph that are identified by a given set of keys. Although the problem is proved to be intractable, and cannot be parallelized in logarithmic rounds, we provide two parallel scalable algorithms for it. In addition, to catch numeric inconsistencies in real-life graphs, we extend graph functional dependencies with linear arithmetic expressions and comparison predicates, referred to as NGDs. Indeed, NGDs strike a balance between expressivity and complexity, since if we allow non-linear arithmetic expressions, even of degree at most 2, the satisfiability and implication problems become undecidable. A localizable incremental algorithm is developed to detect errors using NGDs, where the cost is determined by small neighbors of nodes in the updates instead of the entire graph. Finally, a rule-based method to clean graphs is proposed. We extend graph entity dependencies (GEDs) as data quality rules. Given a graph, a set of GEDs and a block of ground truth, we fix violations of GEDs in the graph by combining data repairing and object identification. The method finds certain fixes to errors detected by GEDs, i.e., as long as the GEDs and the ground truth are correct, the fixes are assured correct as their logical consequences. Several fundamental results underlying the method are established, and an algorithm is developed to implement the method. We also parallelize the method and guarantee to reduce its running time with the increase of processors.
16
Kuhnert, Sebastian Verfasser], Johannes [Akademischer Betreuer] Köbler, Nicole [Akademischer Betreuer] Schweikardt, and Martin [Akademischer Betreuer] [Grohe. "Space efficient algorithms for graph isomorphism and representation / Sebastian Kuhnert. Gutachter: Johannes Köbler ; Nicole Schweikardt ; Martin Grohe." Berlin : Mathematisch-Naturwissenschaftliche Fakultät, 2016. http://d-nb.info/1090965648/34.
Full text
17
Neuen, Daniel [Verfasser], Martin [Akademischer Betreuer] Grohe, Pascal [Akademischer Betreuer] Schweitzer, and László [Akademischer Betreuer] Babai. "The power of algorithmic approaches to the graph isomorphism problem / Daniel Neuen ; Martin Grohe, Pascal Schweitzer, László Babai." Aachen : Universitätsbibliothek der RWTH Aachen, 2019. http://d-nb.info/1216040826/34.
Full text
18
Wiebking, Daniel [Verfasser], Martin [Akademischer Betreuer] Grohe, Pascal [Akademischer Betreuer] Schweitzer, and Jacobo [Akademischer Betreuer] Torán. "A decomposition-compatible canonization framework for the graph isomorphism problem / Daniel Wiebking ; Martin Grohe, Pascal Schweitzer, Jacobo Torán." Aachen : Universitätsbibliothek der RWTH Aachen, 2021. http://d-nb.info/1240480377/34.
Full text
19
Stejskal, Roman. "Zjišťování izomorfizmu grafů v databázi." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2008. http://www.nusl.cz/ntk/nusl-236007.
Full textAbstract:
This project introduces history and basic notions of the graph theory. It describes graph theory problems, possible graph representations and practical graph management in databases. Aims to subgraph and graph isomorphism. It describes possible ways to find graph isomorphism and chosen algorithms for subgraph and graph isomorphism. The experimental part aims to comparing two implemented algorithms. These are Ullmann and VF2 algorithm. Also searches difference between graphs stored in memory and graphs stored in database.
20
Minot, Maël. "Investigating decomposition methods for the maximum common subgraph and sum colouring problems." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSEI120/document.
Full textAbstract:
Notre objectif est d’évaluer et de rendre opérationnelle la décomposition de problèmes d’optimisation sous contraintes. Nous nous sommes intéressés à deux problèmes en particulier : le problème de la recherche d’un plus grand sous-graphe commun (MCIS), et le problème de somme coloration minimale (MSCP). Il s’agit de problèmes NP-difficiles pour lesquels les approches de résolution complètes passent difficilement à l’échelle, et nous proposons de les améliorer à cet égard en décomposant ces problèmes en sous-problèmes indépendants. Les décompositions que nous proposons s’appuient sur la structure du problème initial pour créer des sous-problèmes de tailles équilibrées. Pour le MCIS, nous introduisons une décomposition basée sur la structure du graphe de compatibilité, et nous montrons que cette décomposition permet d’obtenir des sous-problèmes plus équilibrés que la méthode EPS classiquement utilisée pour paralléliser la résolution de problèmes en programmation par contraintes. Pour le MSCP, nous introduisons une nouvelle décomposition arborescente de hauteur bornée, et nous montrons comment tirer partie de la complémentarité de la programmation par contraintes et de la programmation linéaire en nombres entiers pour obtenir et résoudre les sous-problèmes indépendants qui en découlent. Nous proposons également une approche portfolio qui utilise des techniques d’apprentissage automatique pour choisir dynamiquement l’approche la plus performante en fonction du problème à résoudreThe objective of this thesis is, from a general standpoint, to design and evaluate decomposition methods for solving constrained optimisation problems. Two optimisation problems in particular are considered: the maximum common induced subgraph problem, in which the largest common part between two graphs is to be found, and the sum colouring problem, where a graph must be coloured in a way that minimises a sum of weights induced by the employed colours. The maximum common subgraph (MCIS) problem is notably difficult, with a strong applicability in domains such as biology, chemistry and image processing, where the need to measure the similarity between structured objects represented by graphs may arise. The outstanding difficulty of this problem makes it strongly advisable to employ a decomposition method, possibly coupled with a parallelisation of the solution process. However, existing decomposition methods are not well suited to solve the MCIS problem: some lead to a poor balance between subproblems, while others, like tree decomposition, are downright inapplicable. To enable the structural decomposition of such problems, Chmeiss et al. proposed an approach, TR-decomposition, acting at a low level: the microstructure of the problem. This approach had yet to be applied to the MCIS problem. We evaluate it in this context, aiming at reducing the size of the search space while also enabling parallelisation. The second problem that caught our interest is the sum colouring problem. It is an NP-hard variant of the widely known classical graph colouring problem. As in most colouring problems, it basically consists in assigning colours to the vertices of a given graph while making sure no neighbour vertices use the same colour. In the sum colouring problem, however, each colour is associated with a weight. The objective is to minimise the sum of the weights of the colours used by every vertex. This leads to generally harder instances than the classical colouring problem, which simply requires to use as few colours as possible. Only a few exact methods have been proposed for this problem. Among them stand notably a constraint programming (CP) model, a branch and bound approach, as well as an integer linear programming (ILP) model. We led an in-depth investigation of CP's capabilities to solve the sum colouring problem, while also looking into ways to make it more efficient. Additionally, we evaluated a combination of integer linear programming and constraint programming, with the intention of conciliating the strong points of these highly complementary approaches. We took inspiration from the classical backtracking bounded by tree decomposition (BTD) approach. We employ a tree decomposition with a strictly bounded height. We then derive profit from the complementarity of our approaches by developing a portfolio approach, able to choose one of the considered approaches automatically by relying on a number of features extracted from each instance
21
Serrat, Yvan. "Un algorithme de vérification du schéma électrique extrait d'un circuit intégré." Grenoble 1, 1987. http://www.theses.fr/1987GRE10007.
Full textAbstract:
L'etude presentee concerne la verification du schema electrique d'un circuit integre obtenu par extraction. Cette verification est basee sur la comparaison du schema electrique extrait avec le schema electrique de reference, utilise par le concepteur pour dessiner le circuit. Du point de vue mathematique, une telle comparaison est equivalente a un test d'isomorphisme effectue sur les graphes associes aux deux schemas. L'algorithme employe prend en compte tous les parametres des graphes (connectivite, type de noeuds, type de liaisons. . . ) pour determiner si oui ou non ces graphes sont isomorphes, avec une complexite abordable, ce qui permet son application a des circuits d'assez grande taille
22
Shafie, Termeh. "Random Multigraphs : Complexity Measures, Probability Models and Statistical Inference." Doctoral thesis, Stockholms universitet, Statistiska institutionen, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:su:diva-82697.
Full textAbstract:
This thesis is concerned with multigraphs and their complexity which is defined and quantified by the distribution of edge multiplicities. Two random multigraph models are considered. The first model is random stub matching (RSM) where the edges are formed by randomly coupling pairs of stubs according to a fixed stub multiplicity sequence. The second model is obtained by independent edge assignments (IEA) according to a common probability distribution over the edge sites. Two different methods for obtaining an approximate IEA model from an RSM model are also presented. In Paper I, multigraphs are analyzed with respect to structure and complexity by using entropy and joint information. The main results include formulae for numbers of graphs of different kinds and their complexity. The local and global structure of multigraphs under RSM are analyzed in Paper II. The distribution of multigraphs under RSM is shown to depend on a single complexity statistic. The distributions under RSM and IEA are used for calculations of moments and entropies, and for comparisons by information divergence. The main results include new formulae for local edge probabilities and probability approximation for simplicity of an RSM multigraph. In Paper III, statistical tests of a simple or composite IEA hypothesis are performed using goodness-of-fit measures. The results indicate that even for very small number of edges, the null distributions of the test statistics under IEA have distributions that are well approximated by their asymptotic χ2-distributions. Paper IV contains the multigraph algorithms that are used for numerical calculations in Papers I-III.
23
Manion, Kendall. "A Lexicographic Product Cancellation Property for Digraphs." VCU Scholars Compass, 2012. http://scholarscompass.vcu.edu/etd/2932.
Full textAbstract:
There are four prominent product graphs in graph theory: Cartesian, strong, direct, and lexicographic. Of these four product graphs, the lexicographic product graph is the least studied. Lexicographic products are not commutative but still have some interesting properties. This paper begins with basic definitions of graph theory, including the definition of a graph, that are needed to understand theorems and proofs that come later. The paper then discusses the lexicographic product of digraphs, denoted $G \circ H$, for some digraphs $G$ and $H$. The paper concludes by proving a cancellation property for the lexicographic product of digraphs $G$, $H$, $A$, and $B$: if $G \circ H \cong A \circ B$ and $|V(G)| = |V(A)|$, then $G \cong A$. It also proves additional cancellation properties for lexicographic product digraphs and the author hopes the final result will provide further insight into tournaments.
24
Sutinuntopas, Somporn. "Applications of Graph Theory and Topology to Combinatorial Designs." Thesis, University of North Texas, 1988. https://digital.library.unt.edu/ark:/67531/metadc331968/.
Full textAbstract:
This dissertation is concerned with the existence and the isomorphism of designs. The first part studies the existence of designs. Chapter I shows how to obtain a design from a difference family. Chapters II to IV study the existence of an affine 3-(p^m,4,λ) design where the v-set is the Galois field GF(p^m). Associated to each prime p, this paper constructs a graph. If the graph has a 1-factor, then a difference family and hence an affine design exists. The question arises of how to determine when the graph has a 1-factor. It is not hard to see that the graph is connected and of even order. Tutte's theorem shows that if the graph is 2-connected and regular of degree three, then the graph has a 1-factor. By using the concept of quadratic reciprocity, this paper shows that if p Ξ 53 or 77 (mod 120), the graph is almost regular of degree three, i.e., every vertex has degree three, except two vertices each have degree tow. Adding an extra edge joining the two vertices with degree tow gives a regular graph of degree three. Also, Tutte proved that if A is an edge of the graph satisfying the above conditions, then it must have a 1-factor which contains A. The second part of the dissertation is concerned with determining if two designs are isomorphic. Here the v-set is any group G and translation by any element in G gives a design automorphism. Given a design B and its difference family D, two topological spaces, B and D, are constructed. We give topological conditions which imply that a design isomorphism is a group isomorphism.
25
Hofton, Antony Edward. "Graph layout using subgraph isomorphisms." Thesis, Durham University, 2000. http://etheses.dur.ac.uk/4337/.
Full textAbstract:
Today, graphs are used for many things. In engineering, graphs are used to design circuits in very large scale integration. In computer science, graphs are used in the representation of the structure of software. They show information such as the flow of data through the program (known as the data flow graph [1]) or the information about the calling sequence of programs (known as the call graph [145]). These graphs consist of many classes of graphs and may occupy a large area and involve a large number of vertices and edges. The manual layout of graphs is a tedious and error prone task. Algorithms for graph layout exist but tend to only produce a 'good' layout when they are applied to specific classes of small graphs. In this thesis, research is presented into a new automatic graph layout technique. Within many graphs, common structures exist. These are structures that produce 'good' layouts that are instantly recognisable and, when combined, can be used to improve the layout of the graphs. In this thesis common structures are given that are present in call graphs. A method of using subgraph isomorphism to detect these common structures is also presented. The method is known as the ANHOF method. This method is implemented in the ANHOF system, and is used to improve the layout of call graphs. The resulting layouts are an improvement over layouts from other algorithms because these common structures are evident and the number of edge crossings, clusters and aspect ratio are improved.
26
Morris, Joy. "Isomorphisms of Cayley graphs." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape9/PQDD_0024/NQ51903.pdf.
Full text
27
Santos, Philippe Leal Freire dos. "Teoria Espectral de Grafos aplicada ao problema de Isomorfismo de Grafos." Universidade Federal do Espírito Santo, 2010. http://repositorio.ufes.br/handle/10/6388.
Full textAbstract:
Made available in DSpace on 2016-12-23T14:33:41Z (GMT). No. of bitstreams: 1
Dissertacao de Philippe Leal Freire dos Santos.pdf: 1222437 bytes, checksum: 0b5ab3d6e8b9f4b4640e53168b2d042d (MD5)
Previous issue date: 2010-08-23In this work we investigated the use of concepts from Spectral Graph Theory (SGT) to support the construction of algorithms that solve the Graph Isomorphism Problem (GIP). Three theoretical results which consider information from the spectrum of the graphs and from the eigenvector centralities were presented. Furthermore, an algorithm for detection of graph isomorphism based on two of these results was proposed. Finally, we present the computational results comparing this algorithm with others from literature.
Neste trabalho investigamos a utilização de conceitos da Teoria Espectral de Grafos (TEG) a fim de auxiliar a construção de algoritmos que solucionem o Problema de Isomorfismo de Grafos (PIG). Três resultados teóricos que consideram informações do espectro e das centralidades de autovetor dos vértices dos grafos foram apresentados. Além disso, foi proposto um algoritmo para detecção de isomorfismo de grafos baseado em dois destes resultados. Por fim, apresentamos os resultados computacionais da comparação deste algoritmo com outros da literatura
28
Saeed, Mohamed Ahmed. "Approche algébrique sur l'équivalence de codes." Thesis, Normandie, 2017. http://www.theses.fr/2017NORMR034/document.
Full textAbstract:
Le problème d’´équivalence de code joue un rôle important dans la théorie de code et la cryptographie basée sur le code. Cela est dû à son importance dans la classification des codes ainsi que dans la construction et la cryptanalyse des cryptosystèmes à base de codes. Il est également lié à un problème ouvert d’isomorphisme de graphes, un problème bien connu dans le domaine de la théorie de la complexité. Nous prouvons pour les codes ayant un hull trivial qu’il existe une réduction polynomiale de l’équivalence par permutation de codes à l’isomorphisme de graphes. Cela montre que cette sous-classe d’équivalence de permutation n’est pas plus dure que l’isomorphisme de graphes. Nous introduisons une nouvelle méthode pour résoudre le problème d’équivalence de code. Nous développons des approches algébriques pour résoudre le problème dans ses deux versions : en permutation et en diagonale. Nous construisons un système algébrique en établissant des relations entre les matrices génératrices et les matrices de parité des codes équivalents. Nous nous retrouvons avecun système plusieurs variables d’équations linéaires et quadratiques qui peut être résolu en utilisant des outils algébriques tels que les bases de Groebner et les techniques associées. Il est possible en théorie de résoudre l’équivalence de code avec des techniques utilisant des bases de Groebner. Cependant, le calcul en pratique devient complexe à mesure que la longueur du code augmente. Nous avons introduit plusieurs améliorations telles que la linéarisation par bloc et l’action de Frobenius. En utilisant ces techniques, nous identifions de nombreux cas où le problème d’équivalence de permutation peut être résolu efficacement. Notre méthode d’équivalence diagonale résout efficacement le problème dans les corps de petites tailles, à savoir F3 et F4. L’augmentation de la taille du corps entraîne une augmentation du nombre de variables dans notre système algébrique, ce qui le rend difficile à résoudre. Nous nous intéressons enfin au problème d’isomorphisme de graphes en considérant un système algébrique quadratique pour l’isomorphisme de graphes. Pour des instances tirées aléatoirement, le système possède des propriétés intéressantes en termes de rang de la partie linéaire et du nombre de variables. Nousrésolvons efficacement le problème d’isomorphisme de graphes pour des graphes aléatoires avec un grand nombre de sommets, et également pour certains graphes réguliers tels que ceux de Petersen, Cubical et Wagner.123Code equivalence problem plays an important role in coding theory and code based cryptography.That is due to its significance in classification of codes and also construction and cryptanalysis of code based cryptosystems. It is also related to the long standing problem of graph isomorphism, a well-known problem in the world of complexity theory. We introduce new method for solving code equivalence problem. We develop algebraic approaches to solve the problem in its permutation and diagonal versions. We build algebraic system by establishing relations between generator matrices and parity check matrices of the equivalent codes. We end up with system of multivariables of linear and quadratic equations which can be solved using algebraic tools such as Groebner basis and related techniques. By using Groebner basis techniques we can solve the code equivalence but the computation becomes complex as the length of the code increases. We introduced several improvements such as block linearization and Frobenius action. Using these techniques we identify many cases where permutation equivalence problem can be solved efficiently. Our method for diagonal equivalence solves the problem efficiently in small fields, namely F3 and F4. The increase in the field size results in an increase in the number of variables in our algebraic system which makes it difficult to solve. We introduce a new reduction from permutation code equivalence when the hull is trivial to graph isomorphism. This shows that this subclass of permutation equivalence is not harder than graph isomorphism.Using this reduction we obtain an algebraic system for graph isomorphism with interesting properties in terms of the rank of the linear part and the number of variables. We solve the graph isomorphism problem efficiently for random graphs with large number of vertices and also for some regular graphs such as Petersen, Cubical and Wagner Graphs
29
Hashimoto, Marcelo. "Detecção de objetos por reconhecimento de grafos-chave." Universidade de São Paulo, 2012. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-22012014-080625/.
Full textAbstract:
Detecção de objetos é um problema clássico em visão computacional, presente em aplicações como vigilância automatizada, análise de imagens médicas e recuperação de informação. Dentre as abordagens existentes na literatura para resolver esse problema, destacam-se métodos baseados em reconhecimento de pontos-chave que podem ser interpretados como diferentes implementações de um mesmo arcabouço. O objetivo desta pesquisa de doutorado é desenvolver e avaliar uma versão generalizada desse arcabouço, na qual reconhecimento de pontos-chave é substituído por reconhecimento de grafos-chave. O potencial da pesquisa reside na riqueza de informação que um grafo pode apresentar antes e depois de ser reconhecido. A dificuldade da pesquisa reside nos problemas que podem ser causados por essa riqueza, como maldição da dimensionalidade e complexidade computacional. Três contribuições serão incluídas na tese: a descrição detalhada de um arcabouço para detecção de objetos baseado em grafos-chave, implementações fiéis que demonstram sua viabilidade e resultados experimentais que demonstram seu desempenho.Object detection is a classic problem in computer vision, present in applications such as automated surveillance, medical image analysis and information retrieval. Among the existing approaches in the literature to solve this problem, we can highlight methods based on keypoint recognition that can be interpreted as different implementations of a same framework. The objective of this PhD thesis is to develop and evaluate a generalized version of this framework, on which keypoint recognition is replaced by keygraph recognition. The potential of the research resides in the information richness that a graph can present before and after being recognized. The difficulty of the research resides in the problems that can be caused by this richness, such as curse of dimensionality and computational complexity. Three contributions are included in the thesis: the detailed description of a keygraph-based framework for object detection, faithful implementations that demonstrate its feasibility and experimental results that demonstrate its performance.
30
Oberoi, Kamaldeep Singh. "Modélisation spatio-temporelle du trafic routier en milieu urbain." Thesis, Normandie, 2019. http://www.theses.fr/2019NORMR075/document.
Full textAbstract:
Le domaine de la modélisation du trafic routier vise à comprendre son évolution. Dans les dernières années, plusieurs modèles du trafic ont été proposés dans l’objectif de géolocaliser les embouteillages au sein du trafic, détecter des motifs dans le trafic routier, estimer l’état du trafic etc. La plupart des modèles proposés considèrent le trafic routier en termes de ses constituants ou comme une entité agrégée en fonction de l’échelle choisie et expliquent l’évolution du trafic quantitativement en tenant compte des relations entre les variables de trafic comme le flot, la densité et la vitesse. Ces modèles décrivent le trafic en utilisant des données très précises acquises par différents capteurs. La précision des données rend son calcul coûteux en termes de ressources requises. Une des solutions à ce problème est la représentation qualitative du trafic routier qui réduit le nombre de ressources de traitement nécessaires. Puisque le trafic routier est un phénomène spatio-temporel, les modèles proposés pour représenter ce type de phénomène pourraient être appliqués dans le cas du trafic routier. Les modèles spatio-temporels, proposés par la communauté de l’Analyse Spatio-Temporelle, ont comme objectif la représentation d’un phénomène tant du point de vue qualitatif que quantitatif. Certains de ces modèles proposent une discrétisation des phénomènes modélisés en considérant un phénomène comme constitué d’entités. Appliquée au trafic routier, cette notion permet d’identifier différentes entités, comme les véhicules, les piétons, les bâtiments etc., qui le constituent. Ces entités influent sur l’évolution du trafic. Les modèles spatio-temporels qualitatifs définissent l’effet des différentes entités les unes sur les autres en terme de relations spatiales. L’évolution spatio-temporelle du phénomène modélisé est représenté par la variation temporelle de ces relations. La prise en compte des entités du trafic et des relations spatiales formalise une structure qui peut être représentée en utilisant un graphe, où les nœuds modélisent des entités et les arcs des relations spatiales. Par conséquent, l’évolution du trafic, modélisée via ce graphe, devient l’évolution du graphe et peut être représenté en terme de la variation de la structure du graphe ainsi que celle des attributs de ses nœuds et de ses arcs. Dans cette thèse, nous proposons une modélisation du trafic routier de ce type basée sur la théorie des graphes. Une des applications à la modélisation du trafic routier est la détection des motifs pertinents au sein du trafic. Dans les modèles du trafic existants, les motifs détectés sont statistiques et sont représentés en utilisant des caractéristiques numériques. Le modèle que nous pro posons dans cette thèse met en avant la structure représentant le trafic routier et peut donc être utilisé pour définir des motifs structurels du trafic qui prennent en compte des différentes entités du trafic et leurs relations. Ces motifs structurels sont sous-jacents à une modélisation sous forme de graphe dynamique. Dans cette thèse, nous proposons un algorithme pour détecter ces motifs structurels du trafic dans le graphe spatio-temporel représentant le trafic routier. Ce problème est formalisé comme celui de l’isomorphisme de sous-graphe pour des graphes dynamiques. L’algorithme proposé est évalué en fonction desdifférents paramètres de graphesFor past several decades, researchers have been interested in understanding traffic evolution, hence, have proposed various traffic models to identify bottleneck locations where traffic congestion occurs, to detect traffic patterns, to predict traffic states etc. Most of the existing models consider traffic as many-particle system, describe it using different scales of representation and explain its evolution quantitatively by deducing relations between traffic variables like flow, density and speed. Such models are mainly focused on computing precise information about traffic using acquired traffic data. However, computation of such precise information requires more processing resources. A way to remedy this problem is to consider traffic evolution in qualitative terms which reduces the required number of processing resources. Since traffic is spatio-temporal in nature, the models which deal with spatio-temporal phenomenon can be applied in case of traffic. Such models represent spatio-temporal phenomenon from qualitative as well as quantitative standpoints. Depending on the intended application, some models are able to differentiate between various entities taking part in the phenomenon, which proves useful in case of traffic since different objects like vehicles, buildings, pedestrians, bicycles etc., directly affecting traffic evolution, can be included in traffic models. Qualitative spatio-temporal models consider the effects of different entities on each other in terms of spatial relations between them and spatio-temporal evolution of the modeled phenomenon is described in terms of variation in such relations over time. Considering different traffic constituents and spatial relations between them leads to the formation of a structure which can be abstracted using graph, whose nodes represent individual constituents and edges represent the corresponding spatial relations. As a result, the evolution of traffic, represented using graph, is described in terms of evolution of the graph itself, i. e. change in graph structure and attributes of nodes and edges, with time. In this thesis, we propose such a graph model to represent traffic. As mentioned above, one of the applications of existing traffic models is in detecting traffic patterns. However, since such models consider traffic quantitatively, in terms of acquired traffic data, the patterns detected using such models are statistical (a term employed by Pattern Recognition researchers) in the sense that they are represented using numerical description. Since graph-based traffic model proposed in this thesis represents the structure of traffic, it can be employed to redefine the meaning of traffic patterns from statistical to structural (also a term from Pattern Recognition community). Structural traffic patterns include different traffic constituents and their inter-links and are represented using time-varying graphs. An algorithm to detect a given structural traffic pattern in the spatio-temporal graph representing traffic is proposed in this thesis. It formalizes this problem as subgraph isomorphism for time-varying graphs. In the end, the performance of the algorithm is tested using various graph parameters
31
Rodrigues, Edilson José. "Um algoritmo para o Problema do Isomorfismo de Grafos." reponame:Repositório Institucional da UFABC, 2014.
Find full textAbstract:
Orientador: Prof. Dr. Daniel Morgato MartinDissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciências da Computação, 2014.
Neste trabalho estudamos o Problema do Isomorfismo de Grafos e a sua complexidade para resolvê-lo. Nossa principal contribuição é a proposta de um algoritmo para o caso geral do Problema, baseado no particionamento do conjunto de vértices e em emparelhamentos perfeitos de grafos bipartidos. Estudamos também o algoritmo de Brendan McKay, que é o mais rápido algoritmo para o Problema do Isomorfismo de Grafos conhecido. Ao final, implementamos o algoritmo proposto nesta dissertação e o algoritmo de McKay. Após a comparação dos dois algoritmos, verificamos que os resultados obtidos pelo algoritmo proposto não foram satisfatórios, porém apresentamos possíveis melhorias de como deixá-lo mais eficiente.
In this work we study the Graph Isomorphism Problem and their complexity to solve it. Our main contribution is to propose an algorithm for the general case of the Problem, based on partitioning the set vertex and perfect matchings of bipartite graphs. We also studied the Brendan McKay¿s algorithm, who is the fastest algorithm for the Graph Isomorphism Problem known. At the end, we implemented the algorithm proposed in this dissertation and McKay¿s algorithm. After comparison of the two algorithms, we found that the results obtained by the proposed algorithm were not satisfactory, but improvements are possible as to make it more efficient.
32
Rubalcaba, Roberto Ramon Johnson Peter D. "Fractional domination, fractional packings, and fractional isomorphisms of graphs." Auburn, Ala., 2005. http://repo.lib.auburn.edu/EtdRoot/2005/SPRING/Mathematics/Dissertation/RUBALCABA_ROBERT_56.pdf.
Full text
33
Ševčík, Ivan. "Systém pro vyhledávání chemických struktur." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2018. http://www.nusl.cz/ntk/nusl-385936.
Full textAbstract:
This thesis deals with the problem of searching of structures in large chemical compounds databases. The aim is to design and implement an efficient system that supports two basic types of search, which are identity and substructure search. This task is complicated not only by the large number of entries in databases but also by graph representation of chemical structures, for which many algorithms are hard to solve. The thesis will introduce concepts which will prove useful in solving these problems. A web service is also created as a part of the thesis in order to make the database searching available to the users.
34
Vergara, John Paul C. "Edge-packing by isomorphic subgraphs." Thesis, Virginia Tech, 1990. http://hdl.handle.net/10919/42147.
Full textAbstract:
Maximum G Edge-Packing (E PackG) is the problem of finding the maximum number of edge-disjoint isomorphic copies of a fixed guest graph G in a host graph H. The problem is primarily considered for several guest graphs (stars, paths and cycles) and host graphs (arbitrary graphs, planar graphs and trees). We give polynomial-time algorithms when G is a 2-path or when H is a tree; we show the problem is NP-complete otherwise. Also, we propose straightforward greedy polynomial-time approximation algorithms which are at least 1/|EG| optimal.Master of Science
35
Dalcumune, Edinelço. "Algoritmos quânticos para o problema do isomorfismo de grafos." Laboratório Nacional de Computação Científica, 2008. http://www.lncc.br/tdmc/tde_busca/arquivo.php?codArquivo=152.
Full textAbstract:
O problema do isomorfismo de grafos possui aplicações em diversas áreas da ciência. Tal problema não possui uma solução eficiente para o seu caso geral. No presente trabalho, apresentamos os conceitos básicos em teoria de grupos, teoria dos grafos e mecânica quântica. Apresentamos o problema do subgrupo oculto e uma conhecida redução polinomial do problema do isomorfismo de grafos no seu caso geral para o problema do subgrupo oculto sobre o grupo simétrico. Utilizamos um método que reduz o problema do isomorfismo de grafos para o problema de interseção de grupos. Este método utiliza resultados da computação quântica e da teoria dos grupos solúveis, nos permitindo obter uma solução eficiente através de um algoritmo quântico para o problema do isomorfismo de grafos para uma classe particular de grafos.The graph isomorphism problem has applications in several areas of science. This problem has not an efficient solution to its general case. In this work, we present the basic concepts of group theory, graph theory and quantum mechanics. We introduce the hidden subgroup problem and a known polynomial reduction of the graph isomorphism problem in its general case to the hidden subgroup problem on the symmetric group. We use a method that reduces the graph isomorphism problem to the group intersection problem. This method combines results from quantum computing and solvable group theory providing a efficient solution through a quantum algorithm to the graph isomorphism problem for the particular class of graphs.
36
Sanford, Alice Jewel. "Cycle spectra, automorphic uniqueness, and isomorphism classes of generalized Petersen graphs /." Full text available from ProQuest UM Digital Dissertations, 2005. http://0-proquest.umi.com.umiss.lib.olemiss.edu/pqdweb?index=0&did=1264606591&SrchMode=1&sid=3&Fmt=2&VInst=PROD&VType=PQD&RQT=309&VName=PQD&TS=1185199901&clientId=22256.
Full text
37
Hliněnʹy, Petr. "Planar covers of graphs : Negami's conjecture." Diss., Georgia Institute of Technology, 1999. http://hdl.handle.net/1853/29449.
Full text
38
Colledan, Andrea. "On the Hidden Subgroup Problem as a Pivot in Quantum Complexity Theory." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2018. http://amslaurea.unibo.it/16112/.
Full textAbstract:
Quantum computing has opened the way to new algorithms that can efficiently solve problems that have always been deemed intractable. However, since quantum algorithms are hard to design, the necessity to find a generalization of these problems arises. Such necessity is satisfied by the hidden subgroup problem (HSP), an abstract problem of group theory which successfully generalizes a large number of intractable problems. The HSP plays a significant role in quantum complexity theory, as efficient algorithms that solve it can be employed to efficiently solve other valuable problems, such as integer factorization, discrete logarithms, graph isomorphism and many others.
In this thesis we give a computational definition of the HSP. We then prove the reducibility of some of the aforementioned problems to the HSP. Lastly, we introduce some essential notions of quantum computing and we present two quantum algorithms that efficiently solve the HSP on Abelian groups.
39
Badar, Muhammad, and Ansir Iqbal. "Polya's Enumeration Theorem : Number of colorings of n-gons and non isomorphic graphs." Thesis, Linnaeus University, School of Computer Science, Physics and Mathematics, 2010. http://urn.kb.se/resolve?urn=urn:nbn:se:lnu:diva-6199.
Full textAbstract:
Polya’s theorem can be used to enumerate objects under permutation groups. Using grouptheory, combinatorics and some examples, Polya’s theorem and Burnside’s lemma arederived. The examples used are a square, pentagon, hexagon and heptagon under theirrespective dihedral groups. Generalization using more permutations and applications tograph theory.Using Polya’s Enumeration theorem, Harary and Palmer [5] give a function whichgives the number of unlabeled graphs n vertices and m edges. We present their work andthe necessary background knowledge.
40
Carletti, Vincenzo. "Exact and inexact methods for graph Similarity in structural pattern recognition." Caen, 2016. http://www.theses.fr/2016CAEN2004.
Full textAbstract:
Les graphes sont utilisés dans de nombreux domaines applicatifs tels que la biologie, les réseaux sociaux, les bases de données,. . . Les graphes permettentt de décrire un ensemble d'objets ainsi que leurs relations. L'analyse de ces objets réclame souvent de mesurer la similarité entre les graphes. Toutefois, en raison de son aspect combinatoire, ce problème est NP complet et estt généralement résolu en utilisant différentes heuristiques. Dans cette thèse nous avons exploré deux approches pour calculer la similarité entre graphes. La première est basé sur l'appariement exact. Nous avons conçu l'algorithme VF3 qui recherche des motifs dans les graphes. La seconde approche est basée sur un appariement inexact qui calcule une approximation efficace de la distance d'édition entre graphes en la modélisant comme un problème de minimisation quadratiqueGraphs are widely employed in many application fields, such as biology, chemistry, social networks, databases and so on. Graphs allow to describe a set of objects together with their relationships. Analyzing these data often requires to measure the similarity between two graphs. Unfortunately, due to its combinatorial nature, this is a NP-Complete problem generally addressed using different kind of heuristics. In this Thesis we have explored two approaches to compute the similarity between graphs. The former is based on the exact graph matching approach. We have designed, VF3, an algorithm aimed to search for pattern structures within graphs. While, the second approach is an inexact graph matching method which aims to compute an efficient approximation of the Graph Edit Distance (GED) as a Quadratic Assignment Problem (QAP)
41
Bloyet, Nicolas. "Caractérisation et plongement de sous-graphes colorés : application à la construction de modèles structures à activité (QSAR)." Thesis, Lorient, 2019. http://www.theses.fr/2019LORIS546.
Full textAbstract:
Dans le domaine de la chimie, il est intéressant de pouvoir estimer des propriétés physico- chimiques de molécules, notamment pour des applications industrielles. Celles-ci sont difficiles à estimer par simulations physique, présentant une complexité temporelle prohibitive. L'émergence des données (publiques ou privées) ouvre toutefois de nouvelles perspectives pour le traitement de ces problèmes par des méthodes statistiques et d'apprentissage automatique. La principale difficulté réside dans la caractérisation des molécules : celles-ci s'apparentent davantage à un réseau d'atomes (autrement dit un graphe coloré) qu'à un vecteur. Or, les méthodes de modélisation statistiques traitent usuellement avec des observations encodées comme telles, d'où la nécessité de méthodes spécifiques, nommées relations structures-activité, traitant des observations encodées sous forme de graphes. Le but de cette thèse est de tirer parti des corpus publics pour apprendre les meilleures représentations possibles de ces structures, et de transférer cette connaissance globale vers des jeux de données plus restreints. Nous nous inspirons pour ce faire de méthodes utilisées en traitement automatique des langages naturels. Pour les mettre en œuvre, des travaux d'ordre plus théorique ont été nécessaires, notamment sur le problème d'isomorphisme de graphes. Les résultats obtenus sur des tâches de classification/régression sont au moins compétitifs avec l'état de l'art, voire meilleurs, en particulier sur des jeux de données restreints, attestant des possibilités d'apprentissage par transfert sur ce domaineIn the field of chemistry, it is interesting to be able to estimate the physicochemical properties of molecules, especially for industrial applications. These are difficult to estimate by physical simulations, as their implementation often present prohibitive time complexity. However, the emergence of data (public or private) opens new perspectives for the treatment of these problems by statistical methods and machine learning. The main difficulty lies in the characterization of molecules: these are more like a network of atoms (in other words a colored graph) than a vector. Unfortunately, statistical modeling methods usually deal with observations encoded as such, hence the need for specific methods able to deal with graphs- encoded observations, called structure-activity relationships. The aim of this thesis is to take advantage of public corpora to learn the best possible representations of these structures, and to transfer this global knowledge to smaller datasets. We adapted methods used in automatic processing of natural languages to achieve this goal. To implement them, more theoretical work was needed, especially on the graph isomorphism problem. The results obtained on classification / regression tasks are at least competitive with the state of the art, and even sometimes better, in particular on restricted data sets, attesting some opportunities for transfer learning in this field
42
Fuchs, Frank. "Contribution à la reconstruction du bâti en milieu urbain, à l'aide d'images aériennes stéréoscopiques à grande échelle : étude d'une approche structurelle." Paris 5, 2001. http://www.theses.fr/2001PA058004.
Full textAbstract:
L'institut géographique national poursuit ses efforts de recherche visant à automatiser la saisie de bases de données localisées. Dans ce cadre, nous abordons le thème du bâti dont nous cherchons une reconstruction des toits dite grande échelle, i. E. Comprenant leur structure interne. Nous utilisons des outils de calcul de modèle numérique d'élévation (MNE) à partir d'images aériennes à forte résolution (10 à 20 cm). Le MNE produit permet de focaliser les travaux de reconstruction sur des surfaces de taille raisonnable. L'approche proposée est structurelle. Elle s'appuie sur une base de modèles exprimée de manière déclarative ce qui confère une certaine souplesse à l'approche. La stratégie générale se compose de trois étapes. La première étape consiste à détecter dans les données initiales, des objets tridimensionnels simples, appelés primitives : segments de droites, portions de plan, façades. La seconde étape consiste à reconstruire un bâtiment à l'aide d'un modèle. Un modèle est un graphe relationnel attribue. Il est mis en correspondance avec un graphe appuie sur les primitives, grâce a des techniques récentes de calcul d'isomorphisme de sous-graphes avec tolérance d'erreur. Celles-ci utilisent le formalisme de distance d’Edition, qui permet d'intégrer une fonction de ressemblance entre un modèle et les primitives détectées. L'emploi d'une grammaire de graphe est proposé, afin de réduire la combinatoire du problème d'appariement. Après mise en correspondance, une reconstruction finale est réalisée. La troisième étape consiste à choisir, parmi les reconstructions effectuées à l'aide de différents modèles, celle qui est la plus adaptée aux données. Le mémoire présente des résultats obtenus en exploitant la méthode sur des scènes aériennes réelles. Il propose également une évaluation de la méthode, dans un cadre automatique. Enfin, après avoir dressé un bilan de la méthode, ce mémoire propose des extensions de ces travaux.
43
Seiller, Thomas. "Logique dans le facteur hyperfini : Géométrie de l' interaction et complexité." Thesis, Aix-Marseille, 2012. http://www.theses.fr/2012AIXM4064.
Full textAbstract:
Cette thèse est une étude de la géométrie de l'interaction dans le facteur hyperfini (GdI5), introduite par Jean-Yves Girard, et de ses liens avec les constructions plus anciennes. Nous commençons par montrer comment obtenir des adjonctions purement géométriques comme une identité entre des ensembles de cycles apparaissant entre des graphes. Il est alors possible, en choisissant une fonction qui mesure les cycles, d'obtenir une adjonction numérique. Nous montrons ensuite comment construire, sur la base d'une adjonction numérique, une géométrie de l'interaction pour la logique linéaire multiplicative additive où les preuves sont interprétées par des graphes. Nous expliquons également comment cette construction permet de définir une sémantique dénotationnelle de MALL, et une notion de vérité. Nous étudions finalement une généralisation de ce cadre afin d'interpréter les exponentielles et le second ordre. Les constructions sur les graphes étant paramétrées par une fonction de mesure des cycles, nous entreprenons ensuite l'étude de deux cas particuliers. Le premier s'avère être une version combinatoire de la GdI5, et nous obtenons donc une interprétation géométrique de l'orthogonalité basée sur le déterminant de Fuglede-Kadison. Le second cas particulier est une version combinatoire des constructions plus anciennes de la géométrie de l'interaction, où l'orthogonalité est basée sur la nilpotence. Ceci permet donc de comprendre le lien entre les différentes versions de la géométrie de l'interaction, et d'en déduire que les deux adjonctions — qui semblent à première vue si différentes — sont des conséquences d'une même identité géométriqueThis work is a study of the geometry of interaction in the hyperfinite factor introduced by Jean-Yves Girard, and of its relations with ancient constructions. We start by showing how to obtain purely geometrical adjunctions as an identity between sets of cycles appearing between graphs. It is then possible, by chosing a function that measures those cycles, to obtain a numerical adjunction. We then show how to construct, on the basis of such a numerical adjunction, a geometry of interaction for multiplicative additive linear logic where proofs are interpreted as graphs. We also explain how to define from this construction a denotational semantics for MALL, and a notion of truth. We extend this setting in order to deal with exponential connectives and show a full soundness result for a variant of elementary linear logic (ELL). Since the constructions on graphs we define are parametrized by a function that measures cycles, we then focus our study to two particular cases. The first case turns out to be a combinatorial version of GoI5, and we thus obtain a geometrical caracterisation of its orthogonality which is based on Fuglede-Kadison determinant. The second particular case we study will giveus a refined version of older constructions of geometry of interaction, where orthogonality is based on nilpotency. This allows us to show how these two versions of GoI, which seem quite different, are related and understand that the respective adjunctions are both consequences of a unique geometrical property. In the last part, we study the notion of subjective truth
44
Chao-WenHuang and 黃昭文. "DNA Computing on Graph Isomorphism Problems." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/51559672163197544025.
Full textAbstract:
博士國立成功大學
資訊工程學系碩博士班
98
Feynman first proposed DNA-based computation in 1961, but his idea was not implemented by experiment for a few decades. By properly manipulating DNA strands as the input instance of the Hamiltonian path problem, Adleman succeeded in solving the problem in a test tube. Since the experimental demonstration of its feasibility, DNA-based computing has been applied to a number of decision or combinatorial optimization problems. In this thesis, we propose a DNA-based graph encoding scheme which can be used to solve some intractable graph problems, such as the subgraph isomorphism problem and its generalized problem - the maximum common subgraph problem, which are known to be NP-complete problems, in the Adleman-Lipton model using polynomial number of basic biological operations.
45
Tsai, Shiang-Yu, and 蔡翔宇. "A Distributed Graph Isomorphism Algorithm - Design and Experiment." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/22818728231374285621.
Full text
46
Beckman, David Eugene. "Investigations in Quantum Computing: Causality and Graph Isomorphism." Thesis, 2004. https://thesis.library.caltech.edu/2139/1/thesis.pdf.
Full textAbstract:
In this thesis I explore two different types of limits on the time complexity of quantum computation---that is, limits on how much time is required to perform a given class of quantum operations on a quantum system. Upper limits can be found by explicit construction; I explore this approach for the problem of determining whether two graphs are isomorphic. Finding lower limits, on the other hand, usually requires appeal to some fundamental principle of the operation under consideration; I use this approach to derive lower limits placed by the requirements of relativistic causality on the time required for implementation of some nonlocal quantum operations. In some situations these limits are attainable, but for other physical spacetime geometries we exhibit classes of operations which do not violate relativistic causality but which are nevertheless not implementable.
47
Lei, Yaohui. "A survey of graph and subgraph isomorphism problems." Thèse, 2003. http://hdl.handle.net/1866/14540.
Full text
48
Ho, Cheng-Tao, and 何承道. "HybirdGMiner：The Mining Strategy on Frequent Isomorphism Graph Structure." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/4n77ys.
Full textAbstract:
碩士國立中央大學
資訊工程研究所
94
As the mining of frequent itemsets and sequential patterns became more mature, it is very natural that we would want to explore other patterns such as graph structures. Graph mining has very wide applications, such as chemistry, biology and computer networks. The main challenge in graph mining is how to solve the graph/ subgraph isomorphism problems. Thus, we propose an algorithm that combined previous pattern mining skills and some graph mining techniques to mine all frequent subgraph patterns efficiently. Our algorithm adopts canonical form to avoid the duplicate enumeration, and used an effective embedding list structure to avert the subgraph isomorphism checking completely. Our empirical study on synthetic and real datasets demonstrates that HybridGMiner achieves a substantial performance gain over the algorithm gSpan.
49
Chiang, Yi-yang, and 江怡洋. "An Efficient Screening Algorithm for Inexact Sub-graph Isomorphism." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/95898697459733375861.
Full textAbstract:
碩士逢甲大學
資訊工程所
94
Matching inexact sub-graph of attributed relational graphs is a combinatorial optimization problem of difficulty with the constraint of structure consistence. This thesis proposes an efficient screening algorithm to solve the inexact sub-graph isomorphism problems by incrementally reducing the infeasible search space. Hence, searching for near optimal solutions can be confined in a relatively small feasible space. The screening algorithm mainly consists of three stages: Construction, Pruning and Evaluation. The aim of the Construction stage is, by using given tolerances of attribute values, to efficiently choice initial candidates for individual vertices and edges from each label mapping between two graphs. The Pruning stage iteratively eliminates most of these vertices and edge candidates that lead to infeasible combinations by considering the whole topological structure. Consequently, the Evaluation stage, the desired near optimal solutions can be obtained from evaluating all mappings consisted with the remaining candidates based on the objective function measure. This screening algorithm can also work efficiently using a zero tolerance for exact sub-graph isomorphism. Simulation result indicates that near optimal solutions can be obtained by using few pruning iterations and a small number of objective function evaluations.
50
Dona, Daniele. "Growth in finite groups and the Graph Isomorphism Problem." Doctoral thesis, 2020. http://hdl.handle.net/21.11130/00-1735-0000-0005-145F-B.
Full text