Relevant bibliographies by topics / Graph matching

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers
  6. Reports

Academic literature on the topic 'Graph matching'

Author: Grafiati
Published: 4 June 2021
Last updated: 8 June 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Graph matching.'

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.

Journal articles on the topic "Graph matching"

1

Khalashi Ghezelahmad, Somayeh. "On matching integral graphs." Mathematical Sciences 13, no. 4 (October 14, 2019): 387–94. http://dx.doi.org/10.1007/s40096-019-00307-7.

Full text
Abstract:
Abstract The matching polynomial of a graph has coefficients that give the number of matchings in the graph. In this paper, we determine all connected graphs on eight vertices whose matching polynomials have only integer zeros. A graph is matching integral if the zeros of its matching polynomial are all integers. We show that there are exactly two matching integral graphs on eight vertices.
APA, Harvard, Vancouver, ISO, and other styles
2

Ma, Tianlong, Yaping Mao, Eddie Cheng, and Jinling Wang. "Fractional Matching Preclusion for (n, k)-Star Graphs." Parallel Processing Letters 28, no. 04 (December 2018): 1850017. http://dx.doi.org/10.1142/s0129626418500172.

Full text
Abstract:
The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. As a generalization, Liu and Liu introduced the concept of fractional matching preclusion number in 2017. The Fractional Matching Preclusion Number (FMP number) of G is the minimum number of edges whose deletion leaves the resulting graph without a fractional perfect matching. The Fractional Strong Matching Preclusion Number (FSMP number) of G is the minimum number of vertices and/or edges whose deletion leaves the resulting graph without a fractional perfect matching. In this paper, we obtain the FMP number and the FSMP number for (n, k)-star graphs. In addition, all the optimal fractional strong matching preclusion sets of these graphs are categorized.
APA, Harvard, Vancouver, ISO, and other styles
3

LÜ, HUAZHONG, and TINGZENG WU. "Fractional Matching Preclusion for Restricted Hypercube-Like Graphs." Journal of Interconnection Networks 19, no. 03 (September 2019): 1940010. http://dx.doi.org/10.1142/s0219265919400103.

Full text
Abstract:
The restricted hypercube-like graphs, variants of the hypercube, were proposed as desired interconnection networks of parallel systems. The matching preclusion number of a graph is the minimum number of edges whose deletion results in the graph with neither perfect matchings nor almost perfect matchings. The fractional perfect matching preclusion and fractional strong perfect matching preclusion are generalizations of the matching preclusion. In this paper, we obtain fractional matching preclusion number and fractional strong matching preclusion number of restricted hypercube-like graphs, which extend some known results.
APA, Harvard, Vancouver, ISO, and other styles
4

Alishahi, Meysam, and Hajiabolhassan Hossein. "On the Chromatic Number of Matching Kneser Graphs." Combinatorics, Probability and Computing 29, no. 1 (September 12, 2019): 1–21. http://dx.doi.org/10.1017/s0963548319000178.

Full text
Abstract:
AbstractIn an earlier paper, the present authors (2015) introduced the altermatic number of graphs and used Tucker’s lemma, an equivalent combinatorial version of the Borsuk–Ulam theorem, to prove that the altermatic number is a lower bound for chromatic number. A matching Kneser graph is a graph whose vertex set consists of all matchings of a specified size in a host graph and two vertices are adjacent if their corresponding matchings are edge-disjoint. Some well-known families of graphs such as Kneser graphs, Schrijver graphs and permutation graphs can be represented by matching Kneser graphs. In this paper, unifying and generalizing some earlier works by Lovász (1978) and Schrijver (1978), we determine the chromatic number of a large family of matching Kneser graphs by specifying their altermatic number. In particular, we determine the chromatic number of these matching Kneser graphs in terms of the generalized Turán number of matchings.
APA, Harvard, Vancouver, ISO, and other styles
5

Anantapantula, Sai, Christopher Melekian, and Eddie Cheng. "Matching Preclusion for the Shuffle-Cubes." Parallel Processing Letters 28, no. 03 (September 2018): 1850012. http://dx.doi.org/10.1142/s0129626418500123.

Full text
Abstract:
The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. A graph is maximally matched if its matching preclusion number is equal to its minimum degree, and is super matched if the matching preclusion number can only be achieved by deleting all edges incident to a single vertex. In this paper, we determine the matching preclusion number and classify the optimal matching preclusion sets for the shuffle-cube graphs, a variant of the well-known hypercubes.
APA, Harvard, Vancouver, ISO, and other styles
6

CHENG, EDDIE, and OMER SIDDIQUI. "Strong Matching Preclusion of Arrangement Graphs." Journal of Interconnection Networks 16, no. 02 (June 2016): 1650004. http://dx.doi.org/10.1142/s0219265916500043.

Full text
Abstract:
The strong matching preclusion number of a graph is the minimum number of vertices and edges whose deletion results in a graph with neither perfect matchings nor almost-perfect matchings. This is an extension of the matching preclusion problem that was introduced by Park and Ihm. The class of arrangement graphs was introduced as a common generalization of the star graphs and alternating group graphs, and to provide an even richer class of interconnection networks. In this paper, the goal is to find the strong matching preclusion number of arrangement graphs and to categorize all optimal strong matching preclusion sets of these graphs.
APA, Harvard, Vancouver, ISO, and other styles
7

CHENG, EDDIE, and LÁSZLÓ LIPTÁK. "CONDITIONAL MATCHING PRECLUSION FOR (n,k)-STAR GRAPHS." Parallel Processing Letters 23, no. 01 (March 2013): 1350004. http://dx.doi.org/10.1142/s0129626413500047.

Full text
Abstract:
The matching preclusion number of an even graph G, denoted by mp (G), is the minimum number of edges whose deletion leaves the resulting graph without perfect matchings. The conditional matching preclusion number of an even graph G, denoted by mp 1(G), is the minimum number of edges whose deletion leaves the resulting graph with neither perfect matchings nor isolated vertices. The class of (n,k)-star graphs is a popular class of interconnection networks for which the matching preclusion number and the classification of the corresponding optimal solutions were known. However, the conditional version of this problem was open. In this paper, we determine the conditional matching preclusion for (n,k)-star graphs as well as classify the corresponding optimal solutions via several new results. In addition, an alternate proof of the results on the matching preclusion problem will also be given.
APA, Harvard, Vancouver, ISO, and other styles
8

Wang, Xia, Tianlong Ma, Jun Yin, and Chengfu Ye. "Fractional matching preclusion for radix triangular mesh." Discrete Mathematics, Algorithms and Applications 11, no. 04 (August 2019): 1950048. http://dx.doi.org/10.1142/s1793830919500484.

Full text
Abstract:
The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. As a generalization, Liu and Liu recently introduced the concept of fractional matching preclusion number. The fractional matching preclusion number (FMP number) of [Formula: see text], denoted by [Formula: see text], is the minimum number of edges whose deletion leaves the resulting graph without a fractional perfect matching. The fractional strong matching preclusion number (FSMP number) of [Formula: see text], denoted by [Formula: see text], is the minimum number of vertices and edges whose deletion leaves the resulting graph without a fractional perfect matching. In this paper, we study the fractional matching preclusion number and the fractional strong matching preclusion number for the radix triangular mesh [Formula: see text], and all the optimal fractional matching preclusion sets and fractional strong matching preclusion sets of these graphs are categorized.
APA, Harvard, Vancouver, ISO, and other styles
9

BONNEVILLE, PHILIP, EDDIE CHENG, and JOSEPH RENZI. "STRONG MATCHING PRECLUSION FOR THE ALTERNATING GROUP GRAPHS AND SPLIT-STARS." Journal of Interconnection Networks 12, no. 04 (December 2011): 277–98. http://dx.doi.org/10.1142/s0219265911003003.

Full text
Abstract:
The strong matching preclusion number of a graph is the minimum number of vertices and edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. This is an extension of the matching preclusion problem and has recently been introduced by Park and Ihm.15 In this paper, we examine properties of strong matching preclusion for alternating group graphs, by finding their strong matching preclusion numbers and categorizing all optimal solutions. More importantly, we prove a general result on taking a Cartesian product of a graph with K2 (an edge) to obtain the corresponding results for split-stars.
APA, Harvard, Vancouver, ISO, and other styles
10

CHENG, EDDIE, DAVID LU, and BRIAN XU. "STRONG MATCHING PRECLUSION OF PANCAKE GRAPHS." Journal of Interconnection Networks 14, no. 02 (June 2013): 1350007. http://dx.doi.org/10.1142/s0219265913500072.

Full text
Abstract:
The strong matching preclusion number of a graph is the minimum number of vertices and edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. This is an extension of the matching preclusion problem that was introduced by Park and Ihm. In this paper, we examine the properties of pancake graphs by finding its strong matching preclusion number and categorizing all optimal solutions.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Graph matching"

1

Jin, Wei. "GRAPH PATTERN MATCHING, APPROXIMATE MATCHING AND DYNAMIC GRAPH INDEXING." Case Western Reserve University School of Graduate Studies / OhioLINK, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=case1307547974.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Zager, Laura (Laura A. ). "Graph similarity and matching." Thesis, Massachusetts Institute of Technology, 2005. http://hdl.handle.net/1721.1/34119.

Full text
Abstract:
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2005.
Includes bibliographical references (p. 85-88).
Measures of graph similarity have a broad array of applications, including comparing chemical structures, navigating complex networks like the World Wide Web, and more recently, analyzing different kinds of biological data. This thesis surveys several different notions of similarity, then focuses on an interesting class of iterative algorithms that use the structural similarity of local neighborhoods to derive pairwise similarity scores between graph elements. We have developed a new similarity measure that uses a linear update to generate both node and edge similarity scores and has desirable convergence properties. This thesis also explores the application of our similarity measure to graph matching. We attempt to correctly position a subgraph GB within a graph GA using a maximum weight matching algorithm applied to the similarity scores between GA and GB. Significant performance improvements are observed when the topological information provided by the similarity measure is combined with additional information about the attributes of the graph elements and their local neighborhoods. Matching results are presented for subgraph matching within randomly-generated graphs; an appendix briefly discusses matching applications in the yeast interactome, a graph representing protein-protein interactions within yeast.
by Laura Zager.
S.M.
APA, Harvard, Vancouver, ISO, and other styles
3

Zhang, Shijie. "Index-based Graph Querying and Matching in Large Graphs." Cleveland, Ohio : Case Western Reserve University, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=case1263256028.

Full text
Abstract:
Thesis(Ph.D.)--Case Western Reserve University, 2010
Title from PDF (viewed on 2010-04-12) Department of Electrical Engineering and Computer Science (EECS) Includes abstract Includes bibliographical references and appendices Available online via the OhioLINK ETD Center
APA, Harvard, Vancouver, ISO, and other styles
4

Solé, Ribalta Albert. "Multiple graph matching and applications." Doctoral thesis, Universitat Rovira i Virgili, 2012. http://hdl.handle.net/10803/86941.

Full text
Abstract:
En aplicaciones de reconocimiento de patrones, los grafos con atributos son en gran medida apropiados. Normalmente, los vértices de los grafos representan partes locales de los objetos i las aristas relaciones entre estas partes locales. No obstante, estas ventajas vienen juntas con un severo inconveniente, la distancia entre dos grafos no puede ser calculada en un tiempo polinómico. Considerando estas características especiales el uso de los prototipos de grafos es necesariamente omnipresente. Las aplicaciones de los prototipos de grafos son extensas, siendo las más habituales clustering, clasificación, reconocimiento de objetos, caracterización de objetos i bases de datos de grafos entre otras. A pesar de la diversidad de aplicaciones de los prototipos de grafos, el objetivo del mismo es equivalente en todas ellas, la representación de un conjunto de grafos. Para construir un prototipo de un grafo todos los elementos del conjunto de enteramiento tienen que ser etiquetados comúnmente. Este etiquetado común consiste en identificar que nodos de que grafos representan el mismo tipo de información en el conjunto de entrenamiento. Una vez este etiquetaje común esta hecho, los atributos locales pueden ser combinados i el prototipo construido. Hasta ahora los algoritmos del estado del arte para calcular este etiquetaje común mancan de efectividad o bases teóricas. En esta tesis, describimos formalmente el problema del etiquetaje global i mostramos una taxonomía de los tipos de algoritmos existentes. Además, proponemos seis nuevos algoritmos para calcular soluciones aproximadas al problema del etiquetaje común. La eficiencia de los algoritmos propuestos es evaluada en diversas bases de datos reales i sintéticas. En la mayoría de experimentos realizados los algoritmos propuestos dan mejores resultados que los existentes en el estado del arte.
In pattern recognition, the use of graphs is, to a great extend, appropriate and advantageous. Usually, vertices of the graph represent local parts of an object while edges represent relations between these local parts. However, its advantages come together with a sever drawback, the distance between two graph cannot be optimally computed in polynomial time. Taking into account this special characteristic the use of graph prototypes becomes ubiquitous. The applicability of graphs prototypes is extensive, being the most common applications clustering, classification, object characterization and graph databases to name some. However, the objective of a graph prototype is equivalent to all applications, the representation of a set of graph. To synthesize a prototype all elements of the set must be mutually labeled. This mutual labeling consists in identifying which nodes of which graphs represent the same information in the training set. Once this mutual labeling is done the set can be characterized and combined to create a graph prototype. We call this initial labeling a common labeling. Up to now, all state of the art algorithms to compute a common labeling lack on either performance or theoretical basis. In this thesis, we formally describe the common labeling problem and we give a clear taxonomy of the types of algorithms. Six new algorithms that rely on different techniques are described to compute a suboptimal solution to the common labeling problem. The performance of the proposed algorithms is evaluated using an artificial and several real datasets. In addition, the algorithms have been evaluated on several real applications. These applications include graph databases and group-wise image registration. In most of the tests and applications evaluated the presented algorithms have showed a great improvement in comparison to state of the art applications.
APA, Harvard, Vancouver, ISO, and other styles
5

Voigt, Konrad. "Structural Graph-based Metamodel Matching." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2012. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-81671.

Full text
Abstract:
Data integration has been, and still is, a challenge for applications processing multiple heterogeneous data sources. Across the domains of schemas, ontologies, and metamodels, this imposes the need for mapping specifications, i.e. the task of discovering semantic correspondences between elements. Support for the development of such mappings has been researched, producing matching systems that automatically propose mapping suggestions. However, especially in the context of metamodel matching the result quality of state of the art matching techniques leaves room for improvement. Although the traditional approach of pair-wise element comparison works on smaller data sets, its quadratic complexity leads to poor runtime and memory performance and eventually to the inability to match, when applied on real-world data. The work presented in this thesis seeks to address these shortcomings. Thereby, we take advantage of the graph structure of metamodels. Consequently, we derive a planar graph edit distance as metamodel similarity metric and mining-based matching to make use of redundant information. We also propose a planar graph-based partitioning to cope with large-scale matching. These techniques are then evaluated using real-world mappings from SAP business integration scenarios and the MDA community. The results demonstrate improvement in quality and managed runtime and memory consumption for large-scale metamodel matching.
APA, Harvard, Vancouver, ISO, and other styles
6

Irniger, Christophe-André. "Graph matching filtering databases of graphs using machine learning techniques." Berlin Aka, 2005. http://deposit.ddb.de/cgi-bin/dokserv?id=2677754&prov=M&dok_var=1&dok_ext=htm.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Lahn, Nathaniel Adam. "A Separator-Based Framework for Graph Matching Problems." Diss., Virginia Tech, 2020. http://hdl.handle.net/10919/98618.

Full text
Abstract:
Given a graph, a matching is a set of vertex-disjoint edges. Graph matchings have been well studied, since they play a fundamental role in algorithmic theory as well as motivate many practical applications. Of particular interest is the problem of finding a maximum cardinality matching of a graph. Also of interest is the weighted variant: the problem of computing a minimum-cost maximum cardinality matching. For an arbitrary graph with m edges and n vertices, there are known, long-standing combinatorial algorithms that compute a maximum cardinality matching in O(m\sqrt{n}) time. For graphs with non-negative integer edge costs at most C, it is known how to compute a minimum-cost maximum cardinality matching in roughly O(m\sqrt{n} log(nC)) time using combinatorial methods. While non-combinatorial methods exist, they are generally impractical and not well understood due to their complexity. As a result, there is great interest in obtaining faster matching algorithms that are purely combinatorial in nature. Improving existing combinatorial algorithms for arbitrary graphs is considered to be a very difficult problem. To make the problem more approachable, it is desirable to make some additional assumptions about the graph. For our work, we make two such assumptions. First, we assume the graph is bipartite. Second, we assume that the graph has a small balanced separator, meaning it is possible to split the graph into two roughly equal-size components by removing a relatively small portion of the graph. Several well-studied classes of graphs have separator-like properties, including planar graphs, minor-free graphs, and geometric graphs. For such graphs, we describe a framework, a general set of techniques for designing efficient algorithms. We demonstrate this framework by applying it to yield polynomial-factor improvements for several open-problems in bipartite matching.
Doctor of Philosophy
Assume we are given a list of objects, and a list of compatible pairs of these objects. A matching consists of a chosen subset of these compatible pairs, where each object participates in at most one chosen pair. For any chosen pair of objects, we say the these two objects are matched. Generally, we seek to maximize the number of compatible matches. A maximum cardinality matching is a matching with the largest possible size. In many cases, there are multiple options for maximizing the number of compatible pairings. While maximizing the size of the matching is often the primary concern, one may also seek to minimize the cost of the matching. This is known as the minimum-cost maximum-cardinality matching problem. These two matching problems have been well studied, since they play a fundamental role in algorithmic theory as well as motivate many practical applications. Our interest is in the design of algorithms for both of these problems that are efficiently scalable, even as the number of objects involved grows very large. To aid in the design of scalable algorithms, we observe that some inputs have good separators, meaning that by removing some subset S of objects, one can divide the remaining objects into two sets V and V', where all pairs of objects between V and V' are incompatible. We design several new algorithms that exploit good separators, and prove that these algorithms scale better than previously existing approaches.
APA, Harvard, Vancouver, ISO, and other styles
8

Ahmed, Algabli Shaima. "Learning the Graph Edit Distance through embedding the graph matching." Doctoral thesis, Universitat Rovira i Virgili, 2020. http://hdl.handle.net/10803/669612.

Full text
Abstract:
Els gràfics són estructures de dades abstractes que s’utilitzen per modelar problemes reals amb dues entitats bàsiques: nodes i vores. Cada node o vèrtex representa un punt d'interès rellevant d'un problema i cada vora representa la relació entre aquests punts. Es poden atribuir nodes i vores per augmentar la precisió del model, cosa que significa que aquests atributs podrien variar des de vectors de característiques fins a etiquetes de descripció. A causa d'aquesta versatilitat, s'han trobat moltes aplicacions en camps com la visió per ordinador, la biomèdica i l'anàlisi de xarxa, etc., la primera part d'aquesta tesi presenta un mètode general per aprendre automàticament els costos d'edició que comporta l'edició de gràfics. Distància. El mètode es basa en incrustar parells de gràfics i el seu mapeig de node a node de veritat terrestre en un espai euclidià. D’aquesta manera, l’algoritme d’aprenentatge no necessita calcular cap concordança de gràfics tolerant als errors, que és l’inconvenient principal d’altres mètodes a causa de la seva intrínseca complexitat computacional exponencial. No obstant això, el mètode d’aprenentatge té la principal restricció que els costos d’edició han de ser constants. A continuació, posem a prova aquest mètode amb diverses bases de dades gràfiques i també l’aplicem per realitzar el registre d’imatges. A la segona part de la tesi, aquest mètode es particularitza a la verificació d’empremtes dactilars. Les dues diferències principals respecte a l’altre mètode són que només definim els costos d’edició de substitució als nodes. Per tant, suposem que els gràfics no tenen arestes. I també, el mètode d’aprenentatge no es basa en una classificació lineal sinó en una regressió lineal.
Los gráficos son estructuras de datos abstractas que se utilizan para modelar problemas reales con dos entidades básicas: nodos y aristas. Cada nodo o vértice representa un punto de interés relevante de un problema, y cada borde representa la relación entre estos puntos. Se podrían atribuir nodos y bordes para aumentar la precisión del modelo, lo que significa que estos atributos podrían variar de vectores de características a etiquetas de descripción. Debido a esta versatilidad, se han encontrado muchas aplicaciones en campos como visión por computadora, biomédicos y análisis de redes, etc. La primera parte de esta tesis presenta un método general para aprender automáticamente los costos de edición involucrados en la Edición de Gráficos Distancia. El método se basa en incrustar pares de gráficos y su mapeo de nodo a nodo de verdad fundamental en un espacio euclidiano. De esta manera, el algoritmo de aprendizaje no necesita calcular ninguna coincidencia de gráfico tolerante a errores, que es el principal inconveniente de otros métodos debido a su complejidad computacional exponencial intrínseca. Sin embargo, el método de aprendizaje tiene la principal restricción de que los costos de edición deben ser constantes. Luego probamos este método con varias bases de datos de gráficos y también lo aplicamos para realizar el registro de imágenes. En la segunda parte de la tesis, este método se especializa en la verificación de huellas digitales. Las dos diferencias principales con respecto al otro método son que solo definimos los costos de edición de sustitución en los nodos. Por lo tanto, suponemos que los gráficos no tienen aristas. Y también, el método de aprendizaje no se basa en una clasificación lineal sino en una regresión lineal.
Graphs are abstract data structures used to model real problems with two basic entities: nodes and edges. Each node or vertex represents a relevant point of interest of a problem, and each edge represents the relationship between these points. Nodes and edges could be attributed to increase the accuracy of the model, which means that these attributes could vary from feature vectors to description labels. Due to this versatility, many applications have been found in fields such as computer vision, biomedics, and network analysis, and so on .The first part of this thesis presents a general method to automatically learn the edit costs involved in the Graph Edit Distance. The method is based on embedding pairs of graphs and their ground-truth node-tonode mapping into a Euclidean space. In this way, the learning algorithm does not need to compute any Error-Tolerant Graph Matching, which is the main drawback of other methods due to its intrinsic exponential computational complexity. Nevertheless, the learning method has the main restriction that edit costs have to be constant. Then we test this method with several graph databases and also we apply it to perform image registration. In the second part of the thesis, this method is particularized to fingerprint verification. The two main differences with respect to the other method are that we only define the substitution edit costs on the nodes. Thus, we assume graphs do not have edges. And also, the learning method is not based on a linear classification but on a linear regression.
APA, Harvard, Vancouver, ISO, and other styles
9

Wu, Yinghui. "Extending graph homomorphism and simulation for real life graph matching." Thesis, University of Edinburgh, 2011. http://hdl.handle.net/1842/5022.

Full text
Abstract:
Among the vital problems in a variety of emerging applications is the graph matching problem, which is to determine whether two graphs are similar, and if so, find all the valid matches in one graph for the other, based on specified metrics. Traditional graph matching approaches are mostly based on graph homomorphism and isomorphism, falling short of capturing both structural and semantic similarity in real life applications. Moreover, it is preferable while difficult to find all matches with high accuracy over complex graphs. Worse still, the graph structures in real life applications constantly bear modifications. In response to these challenges, this thesis presents a series of approaches for ef?ciently solving graph matching problems, over both static and dynamic real life graphs. Firstly, the thesis extends graph homomorphism and subgraph isomorphism, respectively, by mapping edges from one graph to paths in another, and by measuring the semantic similarity of nodes. The graph similarity is then measured by the metrics based on these extensions. Several optimization problems for graph matching based on the new metrics are studied, with approximation algorithms having provable guarantees on match quality developed. Secondly, although being extended in the above work, graph matching is defined in terms of functions, which cannot capture more meaningful matches and is usually hard to compute. In response to this, the thesis proposes a class of graph patterns, in which an edge denotes the connectivity in a data graph within a predefined number of hops. In addition, the thesis defines graph pattern matching based on a notion of bounded simulation relation, an extension of graph simulation. With this revision, graph pattern matching is in cubic-time by providing such an algorithm, rather than intractable. Thirdly, real life graphs often bear multiple edge types. In response to this, the thesis further extends and generalizes the proposed revisions of graph simulation to a more powerful case: a novel set of reachability queries and graph pattern queries, constrained by a subclass of regular path expressions. Several fundamental problems of the queries are studied: containment, equivalence and minimization. The enriched reachability query does not increase the complexity of the above problems, shown by the corresponding algorithms. Moreover, graph pattern queries can be evaluated in cubic time, where two such algorithms are proposed. Finally, real life graphs are frequently updated with small changes. The thesis investigates incremental algorithms for graph pattern matching defined in terms of graph simulation, bounded simulation and subgraph isomorphism. Besides studying the results on the complexity bounds, the thesis provides the experimental study verifying that these incremental algorithms significantly outperform their batch counterparts in response to small changes, using real-life data and synthetic data.
APA, Harvard, Vancouver, ISO, and other styles
10

Wilson, Richard Charles. "Inexact graph matching using symbolic constraints." Thesis, University of York, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.297165.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Graph matching"

1

1944-, Liu Guizhen, ed. Graph factors and matching extensions. Beijing: Higher Education Press, 2009.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

Yu, Qinglin Roger, and Guizhen Liu. Graph Factors and Matching Extensions. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-540-93952-8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Irniger, Christophe-André Mario. Graph matching: Filtering databases of graphs using machine learning techniques. Berlin: AKA, 2005.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
4

Karpiński, Marek. Fast parallel algorithms for graph matching problems. Oxford: Clarendon Press, 1998.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

J, Chipman Laure, and United States. National Aeronautics and Space Administration., eds. A Graph theoretic approach to scene matching. [Washington, DC: National Aeronautics and Space Administration, 1991.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

Lee, Raymond Shu Tak. Invariant object recognition based on elastic graph matching: Theory and applications. Amsterdam: IOS Press, 2003.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

Valiente, Gabriel. Combinatorial pattern matching algorithms in computational biology using Perl and R. Boca Raton: Chapman & Hall/CRC, 2009.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
8

David, Hutchison. Combinatorial Pattern Matching: 20th Annual Symposium, CPM 2009 Lille, France, June 22-24, 2009 Proceedings. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
9

Derigs, Ulrich. Programming in networks and graphs: On the combinatorial background and near-equivalence of network flow and matching algorithms. Berlin: Springer-Verlag, 1988.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
10

Wiskott, Laurenz. Labeled graphs and dynamic link matching for face recognition and scene analysis. Thun: Deutsch, 1995.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "Graph matching"

1

Jiang, X., and H. Bunke. "Graph Matching." In Case-Based Reasoning on Images and Signals, 149–73. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008. http://dx.doi.org/10.1007/978-3-540-73180-1_5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Saoub, Karin R. "Matching and Factors." In Graph Theory, 213–73. Boca Raton: CRC Press, 2021. | Series: Textbooks in mathematics: Chapman and Hall/CRC, 2021. http://dx.doi.org/10.1201/9781138361416-5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Diestel, Reinhard. "Matching Covering and Packing." In Graph Theory, 35–58. Berlin, Heidelberg: Springer Berlin Heidelberg, 2017. http://dx.doi.org/10.1007/978-3-662-53622-3_2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Diestel, Reinhard. "Matching Covering and Packing." In Graph Theory, 35–57. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/978-3-642-14279-6_2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Rahman, Md Saidur. "Matching and Covering." In Basic Graph Theory, 63–75. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-49475-3_5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Yadav, Santosh Kumar. "Matching & Covering." In Advanced Graph Theory, 141–70. Cham: Springer International Publishing, 2023. http://dx.doi.org/10.1007/978-3-031-22562-8_5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Wu, Yinghui, and Arijit Khan. "Graph Pattern Matching." In Encyclopedia of Big Data Technologies, 1–5. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-63962-8_74-1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Wu, Yinghui, and Arijit Khan. "Graph Pattern Matching." In Encyclopedia of Big Data Technologies, 871–75. Cham: Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-319-77525-8_74.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Zhang, Meng, Liang Hu, Qiang Li, and Jiubin Ju. "Weighted Directed Word Graph." In Combinatorial Pattern Matching, 156–67. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11496656_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Ling, Xiang, Lingfei Wu, Chunming Wu, and Shouling Ji. "Graph Neural Networks: Graph Matching." In Graph Neural Networks: Foundations, Frontiers, and Applications, 277–95. Singapore: Springer Singapore, 2022. http://dx.doi.org/10.1007/978-981-16-6054-2_13.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Graph matching"

1

Masquio, Bruno, Paulo Pinto, and Jayme Szwarcfiter. "Algoritmos eficientes para emparelhamentos desconexos em grafos cordais e grafos bloco." In IV Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2019. http://dx.doi.org/10.5753/etc.2019.6390.

Full text
Abstract:
Graph matching problems are well studied and bring great contributions to Graph Theory from both the theoretical and practical points of view. There are numerous studies for unrestricted and weighted/unweighted matchings. More recently, subgraph-restricted matchings have been proposed, which consider properties of the subgraph induced by the vertices of the matching. In this paper, we approach one of these new proposals, disconnected matching, which seeks to study maximum matching, such that the subgraph induced by the matching vertices is disconnected. We have described efficient algorithms to solve the problem for chordal graphs and block graphs based on a theoretical characterization.
APA, Harvard, Vancouver, ISO, and other styles
2

Peng, Yun, Byron Choi, and Jianliang Xu. "Graph Edit Distance Learning via Modeling Optimum Matchings with Constraints." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. California: International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/212.

Full text
Abstract:
Graph edit distance (GED) is a fundamental measure for graph similarity analysis in many real applications. GED computation has known to be NP-hard and many heuristic methods are proposed. GED has two inherent characteristics: multiple optimum node matchings and one-to-one node matching constraints. However, these two characteristics have not been well considered in the existing learning-based methods, which leads to suboptimal models. In this paper, we propose a novel GED-specific loss function that simultaneously encodes the two characteristics. First, we propose an optimal partial node matching-based regularizer to encode multiple optimum node matchings. Second, we propose a plane intersection-based regularizer to impose the one-to-one constraints for the encoded node matchings. We use the graph neural network on the association graph of the two input graphs to learn the cross-graph representation. Our experiments show that our method is 4.2x-103.8x more accurate than the state-of-the-art methods on real-world benchmark graphs.
APA, Harvard, Vancouver, ISO, and other styles
3

Baek, Jinheon, Alham Aji, and Amir Saffari. "Knowledge-Augmented Language Model Prompting for Zero-Shot Knowledge Graph Question Answering." In Proceedings of the First Workshop on Matching From Unstructured and Structured Data (MATCHING 2023). Stroudsburg, PA, USA: Association for Computational Linguistics, 2023. http://dx.doi.org/10.18653/v1/2023.matching-1.7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Qu, Jingwei, Haibin Ling, Chenrui Zhang, Xiaoqing Lyu, and Zhi Tang. "Adaptive Edge Attention for Graph Matching with Outliers." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. California: International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/134.

Full text
Abstract:
Graph matching aims at establishing correspondence between node sets of given graphs while keeping the consistency between their edge sets. However, outliers in practical scenarios and equivalent learning of edge representations in deep learning methods are still challenging. To address these issues, we present an Edge Attention-adaptive Graph Matching (EAGM) network and a novel description of edge features. EAGM transforms the matching relation between two graphs into a node and edge classification problem over their assignment graph. To explore the potential of edges, EAGM learns edge attention on the assignment graph to 1) reveal the impact of each edge on graph matching, as well as 2) adjust the learning of edge representations adaptively. To alleviate issues caused by the outliers, we describe an edge by aggregating the semantic information over the space spanned by the edge. Such rich information provides clear distinctions between different edges (e.g., inlier-inlier edges vs. inlier-outlier edges), which further distinguishes outliers in the view of their associated edges. Extensive experiments demonstrate that EAGM achieves promising matching quality compared with state-of-the-arts, on cases both with and without outliers. Our source code along with the experiments is available at https://github.com/bestwei/EAGM.
APA, Harvard, Vancouver, ISO, and other styles
5

Lyu, Gengyu, Yanan Wu, and Songhe Feng. "Deep Graph Matching for Partial Label Learning." In Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}. California: International Joint Conferences on Artificial Intelligence Organization, 2022. http://dx.doi.org/10.24963/ijcai.2022/459.

Full text
Abstract:
Partial Label Learning (PLL) aims to learn from training data where each instance is associated with a set of candidate labels, among which only one is correct. In this paper, we formulate the task of PLL problem as an ``instance-label'' matching selection problem, and propose a DeepGNN-based graph matching PLL approach to solve it. Specifically, we first construct all instances and labels as graph nodes into two different graphs respectively, and then integrate them into a unified matching graph by connecting each instance to its candidate labels. Afterwards, the graph attention mechanism is adopted to aggregate and update all nodes state on the instance graph to form structural representations for each instance. Finally, each candidate label is embedded into its corresponding instance and derives a matching affinity score for each instance-label correspondence with a progressive cross-entropy loss. Extensive experiments on various data sets have demonstrated the superiority of our proposed method.
APA, Harvard, Vancouver, ISO, and other styles
6

Jin, Di, Luzhi Wang, Yizhen Zheng, Xiang Li, Fei Jiang, Wei Lin, and Shirui Pan. "CGMN: A Contrastive Graph Matching Network for Self-Supervised Graph Similarity Learning." In Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}. California: International Joint Conferences on Artificial Intelligence Organization, 2022. http://dx.doi.org/10.24963/ijcai.2022/292.

Full text
Abstract:
Graph similarity learning refers to calculating the similarity score between two graphs, which is required in many realistic applications, such as visual tracking, graph classification, and collaborative filtering. As most of the existing graph neural networks yield effective graph representations of a single graph, little effort has been made for jointly learning two graph representations and calculating their similarity score. In addition, existing unsupervised graph similarity learning methods are mainly clustering-based, which ignores the valuable information embodied in graph pairs. To this end, we propose a contrastive graph matching network (CGMN) for self-supervised graph similarity learning in order to calculate the similarity between any two input graph objects. Specifically, we generate two augmented views for each graph in a pair respectively. Then, we employ two strategies, namely cross-view interaction and cross-graph interaction, for effective node representation learning. The former is resorted to strengthen the consistency of node representations in two views. The latter is utilized to identify node differences between different graphs. Finally, we transform node representations into graph-level representations via pooling operations for graph similarity computation. We have evaluated CGMN on eight real-world datasets, and the experiment results show that the proposed new approach is superior to the state-of-the-art methods in graph similarity learning downstream tasks.
APA, Harvard, Vancouver, ISO, and other styles
7

Fuchs, Mathias, and Kaspar Riesen. "Matching of Matching-Graphs - A Novel Approach for Graph Classification." In 2020 25th International Conference on Pattern Recognition (ICPR). IEEE, 2021. http://dx.doi.org/10.1109/icpr48806.2021.9411926.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Feng Zhou and F. De la Torre. "Factorized graph matching." In 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, 2012. http://dx.doi.org/10.1109/cvpr.2012.6247667.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Zhou, Feng, and Fernando De la Torre. "Deformable Graph Matching." In 2013 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, 2013. http://dx.doi.org/10.1109/cvpr.2013.376.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Gubichev, Andrey, and Manuel Then. "Graph Pattern Matching." In SIGMOD/PODS'14: International Conference on Management of Data. New York, NY, USA: ACM, 2014. http://dx.doi.org/10.1145/2621934.2621944.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Graph matching"

1

Gabow, Harold N., and Robert E. Tarjan. Faster Scaling Algorithms for General Graph Matching Problems. Fort Belvoir, VA: Defense Technical Information Center, April 1989. http://dx.doi.org/10.21236/ada215112.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Gallagher, B. The State of the Art in Graph-Based Pattern Matching. Office of Scientific and Technical Information (OSTI), March 2006. http://dx.doi.org/10.2172/895418.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Marcus, Sherry E., Albert G. Frantz, and John A. Beyerle. Graph Matching and Link Analysis for Dynamic Planning and Execution. Fort Belvoir, VA: Defense Technical Information Center, September 2002. http://dx.doi.org/10.21236/ada467560.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Mathuria, Aakanksha. Approximate Pattern Matching using Hierarchical Graph Construction and Sparse Distributed Representation. Portland State University Library, January 2000. http://dx.doi.org/10.15760/etd.7453.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Roy, Heather, Kirk Ogaard, and Sue Kase. User Manual and Installation Guide for the Graph Matching Toolkit (GMT) Version 1.0. Fort Belvoir, VA: Defense Technical Information Center, January 2014. http://dx.doi.org/10.21236/ada600703.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Patwardhan, Kedar A., Guillermo Sapiro, and Vassilios Morellas. A Graph-based Foreground Representation and Its Application in Example Based People Matching in Video (PREPRINT). Fort Belvoir, VA: Defense Technical Information Center, January 2007. http://dx.doi.org/10.21236/ada478409.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Plummer, Michael D. Extending Matchings in Graphs: A Survey. Fort Belvoir, VA: Defense Technical Information Center, January 1990. http://dx.doi.org/10.21236/ada234392.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Moeller, Daniel, Ramamohan Paturi, and Moshe Hoffman. Jealousy Graphs: Structure and Complexity of Decentralized Stable Matching. Fort Belvoir, VA: Defense Technical Information Center, January 2013. http://dx.doi.org/10.21236/ada600700.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Graph matching' for particular source types:
Journal articles Dissertations / Theses Books
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography