Journal articles: '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

11

Zhang, Shuangshuang, Yuzhi Xiao, Xia Liu, and Jun Yin. "A Short Note of Strong Matching Preclusion for a Class of Arrangement Graphs." Parallel Processing Letters 30, no. 01 (March 2020): 2050001. http://dx.doi.org/10.1142/s0129626420500012.

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. The strong matching preclusion is a well-studied measure for the network invulnerability in the event of edge failure. In this paper, we obtain the strong matching preclusion number for a class of arrangement graphs and categorize their the strong matching preclusion set, which are a supplement of known results.

APA, Harvard, Vancouver, ISO, and other styles

12

CHENG, EDDIE, LINDA LESNIAK, MARC J. LIPMAN, and LÁSZLÓ LIPTÁK. "MATCHING PRECLUSION FOR ALTERNATING GROUP GRAPHS AND THEIR GENERALIZATIONS." International Journal of Foundations of Computer Science 19, no. 06 (December 2008): 1413–37. http://dx.doi.org/10.1142/s0129054108006364.

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. In this paper, we find this number for the alternating group graphs, Cayley graphs generated by 2-trees and the (n,k)-arrangement graphs. Moreover, we classify all the optimal solutions.

APA, Harvard, Vancouver, ISO, and other styles

13

PANDA, B. S., and D. PRADHAN. "ACYCLIC MATCHINGS IN SUBCLASSES OF BIPARTITE GRAPHS." Discrete Mathematics, Algorithms and Applications 04, no. 04 (December 2012): 1250050. http://dx.doi.org/10.1142/s1793830912500504.

Full text

Abstract:

A set M ⊆ E is called an acyclic matching of a graph G = (V, E) if no two edges in M are adjacent and the subgraph induced by the set of end vertices of the edges of M is acyclic. Given a positive integer k and a graph G = (V, E), the acyclic matching problem is to decide whether G has an acyclic matching of cardinality at least k. Goddard et al. (Discrete Math.293(1–3) (2005) 129–138) introduced the concept of the acyclic matching problem and proved that the acyclic matching problem is NP-complete for general graphs. In this paper, we propose an O(n + m) time algorithm to find a maximum cardinality acyclic matching in a chain graph having n vertices and m edges and obtain an expression for the number of maximum cardinality acyclic matchings in a chain graph. We also propose a dynamic programming-based O(n + m) time algorithm to find a maximum cardinality acyclic matching in a bipartite permutation graph having n vertices and m edges. Finally, we strengthen the complexity result of the acyclic matching problem by showing that this problem remains NP-complete for perfect elimination bipartite graphs.

APA, Harvard, Vancouver, ISO, and other styles

14

Pálvölgyi, Dömötör. "Partitioning to three matchings of given size is NP-complete for bipartite graphs." Acta Universitatis Sapientiae, Informatica 6, no. 2 (December 1, 2014): 206–9. http://dx.doi.org/10.1515/ausi-2015-0004.

Full text

Abstract:

Abstract We show that the problem of deciding whether the edge set of a bipartite graph can be partitioned into three matchings, of size k1, k2 and k3 is NP-complete, even if one of the matchings is required to be perfect. We also show that the problem of deciding whether the edge set of a simple graph contains a perfect matching and a disjoint matching of size k or not is NP-complete, already for bipartite graphs with maximum degree 3. It also follows from our construction that it is NP-complete to decide whether in a bipartite graph there is a perfect matching and a disjoint matching that covers all vertices whose degree is at least 2.

APA, Harvard, Vancouver, ISO, and other styles

15

Gong, Luozhong, and Weijun Liu. "The Ordering of the Unicyclic Graphs with respect to Largest Matching Root with Given Matching Number." Journal of Mathematics 2022 (May 28, 2022): 1–8. http://dx.doi.org/10.1155/2022/3589448.

Full text

Abstract:

The matching roots of a simple connected graph G are the roots of the matching polynomial which is defined as M G x = ∑ k = 0 n / 2 − 1 k m G , k x n − 2 k , where m G , k is the number of the k matchings of G . Let λ 1 G denote the largest matching root of the graph G . In this paper, among the unicyclic graphs of order n , we present the ordering of the unicyclic graphs with matching number 2 according to the λ 1 G values for n ≥ 11 and also determine the graphs with the first and second largest λ 1 G values with matching number 3.

APA, Harvard, Vancouver, ISO, and other styles

16

Wang, Tianzhe, Zetian Jiang, and Junchi Yan. "Multiple Graph Matching and Clustering via Decayed Pairwise Matching Composition." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 02 (April 3, 2020): 1660–67. http://dx.doi.org/10.1609/aaai.v34i02.5528.

Full text

Abstract:

Jointly matching of multiple graphs is challenging and recently has been an active topic in machine learning and computer vision. State-of-the-art methods have been devised, however, to our best knowledge there is no effective mechanism that can explicitly deal with the matching of a mixture of graphs belonging to multiple clusters, e.g., a collection of bikes and bottles. Seeing its practical importance, we propose a novel approach for multiple graph matching and clustering. Firstly, for the traditional multi-graph matching setting, we devise a composition scheme based on a tree structure, which can be seen as in the between of two strong multi-graph matching solvers, i.e., MatchOpt (Yan et al. 2015a) and CAO (Yan et al. 2016a). In particular, it can be more robust than MatchOpt against a set of diverse graphs and more efficient than CAO. Then we further extend the algorithm to the multiple graph matching and clustering setting, by adopting a decaying technique along the composition path, to discount the meaningless matching between graphs in different clusters. Experimental results show the proposed methods achieve excellent trade-off on the traditional multi-graph matching case, and outperform in both matching and clustering accuracy, as well as time efficiency.

APA, Harvard, Vancouver, ISO, and other styles

17

WANG, XIUMEI, WEIPING SHANG, YIXUN LIN, and MARCELO H. CARVALHO. "A CHARACTERIZATION OF PM-COMPACT CLAW-FREE CUBIC GRAPHS." Discrete Mathematics, Algorithms and Applications 06, no. 02 (March 19, 2014): 1450025. http://dx.doi.org/10.1142/s1793830914500256.

Full text

Abstract:

The perfect matching polytope of a graph G is the convex hull of the incidence vectors of all perfect matchings in G. This paper characterizes claw-free cubic graphs whose 1-skeleton graphs of perfect matching polytopes have diameter 1.

APA, Harvard, Vancouver, ISO, and other styles

18

Bhat, K. Arathi, and G. Sudhakara. "Commuting decomposition of Kn1,n2,...,nk through realization of the product A(G)A(GPk )." Special Matrices 6, no. 1 (August 1, 2018): 343–56. http://dx.doi.org/10.1515/spma-2018-0028.

Full text

Abstract:

Abstract In this paper, we introduce the notion of perfect matching property for a k-partition of vertex set of given graph. We consider nontrivial graphs G and GPk , the k-complement of graph G with respect to a kpartition of V(G), to prove that A(G)A(GPk ) is realizable as a graph if and only if P satis_es perfect matching property. For A(G)A(GPk ) = A(Γ) for some graph Γ, we obtain graph parameters such as chromatic number, domination number etc., for those graphs and characterization of P is given for which GPk and Γ are isomorphic. Given a 1-factor graph G with 2n vertices, we propose a partition P for which GPk is a graph of rank r and A(G)A(GPk ) is graphical, where n ≤ r ≤ 2n. Motivated by the result of characterizing decomposable Kn,n into commuting perfect matchings [2], we characterize complete k-partite graph Kn1,n2,...,nk which has a commuting decomposition into a perfect matching and its k-complement.

APA, Harvard, Vancouver, ISO, and other styles

19

Zhao, Jin-Hua. "A local algorithm and its percolation analysis of bipartite z-matching problem." Journal of Statistical Mechanics: Theory and Experiment 2023, no. 5 (May 1, 2023): 053401. http://dx.doi.org/10.1088/1742-5468/acd105.

Full text

Abstract:

Abstract A z-matching on a bipartite graph is a set of edges, among which each vertex of two types of the graph is adjacent to at most 1 and at most z ( ⩾ 1 ) edges, respectively. The z-matching problem concerns finding z-matchings with the maximum size. Our approach to this combinatorial optimization problem is twofold. From an algorithmic perspective, we adopt a local algorithm as a linear approximate solver to find z-matchings on any graph instance, whose basic component is a generalized greedy leaf removal procedure in graph theory. From a theoretical perspective, on uncorrelated random bipartite graphs, we develop a mean-field theory for the percolation phenomenon underlying the local algorithm, leading to an analytical estimation of z-matching sizes on random graphs. Our analytical theory corrects the prediction by belief propagation algorithm at zero-temperature limit in (Kreačić and Bianconi 2019 Europhys. Lett. 126 028001). Besides, our theoretical framework extends a core percolation analysis of k-XORSAT problems to a general context of uncorrelated random hypergraphs with arbitrary degree distributions of factor and variable nodes.

APA, Harvard, Vancouver, ISO, and other styles

20

Li, Yaqi. "Patterns and Line-Adjacency Matrix Strategy on a Game of Induced Matching." Galore International Journal of Applied Sciences and Humanities 7, no. 3 (August 17, 2023): 31–37. http://dx.doi.org/10.52403/gijash.20230304.

Full text

Abstract:

A matching is an independent set of edges in a graph G; an induced matching is a matching with an additional property that no two of its edges are joined by an edge in G. An induced matching M in a graph G is maximal if no other induced matching in G contains M. In the proposed game, players alternate choose edges on a graph while maintaining an induced matching. They continue until the matching is maximal (i.e. no player can choose another edge), and the last player to choose an edge wins. This paper will discuss patterns for this game and prove results on several categories of graphs including Complete Graphs, Path Graphs, Cycle Graphs, and Ladder Graphs. In addition, a novel Line-Adjacency Matrix method has been defined and proved to calculate all possible edges for the next move in a connected graph. Keywords: Induced Matching, Adjacency Matrix, Line-Adjacency Graph

APA, Harvard, Vancouver, ISO, and other styles

21

CHENG, EDDIE, and SACHIN PADMANABHAN. "MATCHING PRECLUSION AND CONDITIONAL MATCHING PRECLUSION FOR CROSSED CUBES." Parallel Processing Letters 22, no. 02 (May 16, 2012): 1250005. http://dx.doi.org/10.1142/s0129626412500053.

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. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings. In this paper, we find the matching preclusion number and the conditional matching preclusion number with the classification of the optimal sets for the class of crossed cubes, an important variant of the class of hypercubes. Indeed, we will establish more general results on the matching preclusion and the conditional matching preclusion problems for a larger class of interconnection networks.

APA, Harvard, Vancouver, ISO, and other styles

22

Bunke, H., and B. T. Messmer. "Recent Advances in Graph Matching." International Journal of Pattern Recognition and Artificial Intelligence 11, no. 01 (February 1997): 169–203. http://dx.doi.org/10.1142/s0218001497000081.

Full text

Abstract:

A powerful and universal data structure with applications invarious subfields of science and engineering is graphs. In computer vision and image analysis, graphs are often used for the representation of structured objects. For example, if the problem is to recognize instances of known objects in an image, then often models, or prototypes, of the known objects are represented by means of graphs and stored in a database. The unknown objects in the input image are extracted by means of suitable preprocessing and segmentation algorithms, and represented by graphs that are analogous to the model graphs. Thus, the problem of object recognition is transformed into a graph matching problem. In this paper, it is assumed that there is an input graph that is given on-line, and a number of model, or prototype, graphs that are known a priori. We present a new approach to subgraph isomorphism detection which is based on a compact representation of the model graphs that is computed off-line. Subgraphs that appear multiple times within the same or within different model graphs are represented only once, thus reducing the computational effort to detect them in an input graph. In the extreme case where all model graphs are highly similar, the run time of the new algorithm becomes independent of the number of model graphs. We also describe an extension of this method to error-correcting graph matching. Furthermore, an approach to subgraph isomorphism detection based on decision trees is proposed. A decision tree is generated from the models in an off-line phase. This decision tree can be used for subgraph isomorphism detection. The time needed for decision tree traversal is only polynomial in terms of the number of nodes of the input graph. Moreover, the time complexity of the decision tree traversal is completely independent on the number of model graphs, regardless of their similarity. However, the size of the decision tree is exponential in the number of nodes of the models. To cut down the space complexity of the decision tree, some pruning strategies are discussed.

APA, Harvard, Vancouver, ISO, and other styles

23

Bartha, Miklós, and Miklós Krész. "On the König deficiency of zero-reducible graphs." Journal of Combinatorial Optimization 39, no. 1 (November 6, 2019): 273–92. http://dx.doi.org/10.1007/s10878-019-00466-2.

Full text

Abstract:

Abstract A confluent and terminating reduction system is introduced for graphs, which preserves the number of their perfect matchings. A union-find algorithm is presented to carry out reduction in almost linear time. The König property is investigated in the context of reduction by introducing the König deficiency of a graph G as the difference between the vertex covering number and the matching number of G. It is shown that the problem of finding the König deficiency of a graph is NP-complete even if we know that the graph reduces to the empty graph. Finally, the König deficiency of graphs G having a vertex v such that $$G-v$$G-v has a unique perfect matching is studied in connection with reduction.

APA, Harvard, Vancouver, ISO, and other styles

24

Zhang, Lixia, and Jianliang Gao. "Incremental Graph Pattern Matching Algorithm for Big Graph Data." Scientific Programming 2018 (2018): 1–8. http://dx.doi.org/10.1155/2018/6749561.

Full text

Abstract:

Graph pattern matching is widely used in big data applications. However, real-world graphs are usually huge and dynamic. A small change in the data graph or pattern graph could cause serious computing cost. Incremental graph matching algorithms can avoid recomputing on the whole graph and reduce the computing cost when the data graph or the pattern graph is updated. The existing incremental algorithm PGC_IncGPM can effectively reduce matching time when no more than half edges of the pattern graph are updated. However, as the number of changed edges increases, the improvement of PGC_IncGPM gradually decreases. To solve this problem, an improved algorithm iDeltaP_IncGPM is developed in this paper. For multiple insertions (resp., deletions) on pattern graphs, iDeltaP_IncGPM determines the nodes’ matching state detection sequence and processes them together. Experimental results show that iDeltaP_IncGPM has higher efficiency and wider application range than PGC_IncGPM.

APA, Harvard, Vancouver, ISO, and other styles

25

FANKHAUSER, STEFAN, KASPAR RIESEN, HORST BUNKE, and PETER DICKINSON. "SUBOPTIMAL GRAPH ISOMORPHISM USING BIPARTITE MATCHING." International Journal of Pattern Recognition and Artificial Intelligence 26, no. 06 (September 2012): 1250013. http://dx.doi.org/10.1142/s0218001412500139.

Full text

Abstract:

Graphs provide us with a flexible and powerful way to represent objects in various areas of computer science. One of the main drawbacks is, however, that many standard algorithms on graphs have a high computational complexity. The present paper considers the problem of graph isomorphism, i.e. checking two graphs for identity. A novel approach for the efficient computation of graph isomorphism is presented. The proposed algorithm is based on bipartite graph matching by means of an assignment algorithm. The algorithmic framework is suboptimal in the sense of possibly rejecting pairs of graphs without making a decision. As an advantage, however, it offers polynomial runtime. In experiments on diverse graph data sets we demonstrate substantial speedups of our proposed method over several standard procedures for graph isomorphism. Furthermore, although the computational framework for isomorphism is suboptimal, we show that the proposed algorithm rejects only very few pairs of graphs and otherwise returns correct results.

APA, Harvard, Vancouver, ISO, and other styles

26

Solomko, Viktoriia, and Vladyslav Sobolev. "Constructing the Mate of Cospectral 5-regular Graphs with and without a Perfect Matching." Mohyla Mathematical Journal 4 (May 19, 2022): 24–27. http://dx.doi.org/10.18523/2617-70804202124-27.

Full text

Abstract:

The problem of finding a perfect matching in an arbitrary simple graph is well known and popular in graph theory. It is used in various fields, such as chemistry, combinatorics, game theory etc. The matching of M in a simple graph G is a set of pairwise nonadjacent edges, ie, those that do not have common vertices. Matching is called perfect if it covers all vertices of the graph, ie each of the vertices of the graph is incidental to exactly one of the edges. By Koenig's theorem, regular bipartite graphs of positive degree always have perfect matching. However, graphs that are not bipartite need further research. Another interesting problem of graph theory is the search for pairwise nonisomorphic cospectral graphs. In addition, it is interesting to find cospectral graphs that have additional properties. For example, finding cospectral graphs with and without a perfect matching. The fact that for each there is a pair of cospectral connected k-regular graphs with and without a perfect matching had been investigated by Blazsik, Cummings and Haemers. The pair of cospectral connected 5-regular graphs with and without a perfect matching is constructed by using Godsil-McKay switching in the paper.

APA, Harvard, Vancouver, ISO, and other styles

27

Abreu, Nair Maria Maia de, Liliana Manuela Gaspar Cerveira da Costa, Carlos Henrique Pereira Nascimento, and Laura Patuzzi. "A Note on the Matching Polytope of a Graph." TEMA (São Carlos) 20, no. 1 (May 20, 2019): 189. http://dx.doi.org/10.5540/tema.2019.020.01.189.

Full text

Abstract:

The matching polytope of a graph G, denoted by M(G), is the convex hull of the set of the incidence vectors of the matchings G. The graph G(M(G)), whose vertices and edges are the vertices and edges of M(G), is the skeleton of the matching polytope of G. In this paper, for an arbitrary graph, we prove that the minimum degree of G(M(G)) is equal to the number of edges of G, generalizing a known result for trees. From this, we identify the vertices of the skeleton with the minimum degree and we prove that the union of stars and triangles characterizes regular skeletons of the matching polytopes of graphs.

APA, Harvard, Vancouver, ISO, and other styles

28

Zhang, Qianzhen, Deke Guo, Xiang Zhao, and Xi Wang. "Continuous matching of evolving patterns over dynamic graph data." World Wide Web 24, no. 3 (April 13, 2021): 721–45. http://dx.doi.org/10.1007/s11280-020-00860-5.

Full text

Abstract:

AbstractNowadays, the scale of various graphs soars rapidly, which imposes a serious challenge to develop processing and analytic algorithms. Among them, graph pattern matching is the one of the most primitive tasks that find a wide spectrum of applications, the performance of which is yet often affected by the size and dynamicity of graphs. In order to handle large dynamic graphs, incremental pattern matching is proposed to avoid re-computing matches of patterns over the entire data graph, hence reducing the matching time and improving the overall execution performance. Due to the complexity of the problem, little work has been reported so far to solve the problem, and most of them only solve the graph pattern matching problem under the scenario of the data graph varying alone. In this article, we are devoted to a more complicated but very practical graph pattern matching problem, continuous matching of evolving patterns over dynamic graph data, and the investigation presents a novel algorithm for continuously pattern matching along with changes of both pattern graph and data graph. Specifically, we propose a concise representation of partial matching solutions, which can help to avoid re-computing matches of the pattern and speed up subsequent matching process. In order to enable the updates of data graph and pattern graph, we propose an incremental maintenance strategy, to efficiently maintain the intermediate results. Moreover, we conceive an effective model for estimating step-wise cost of pattern evaluation to drive the matching process. Extensive experiments verify the superiority of .

APA, Harvard, Vancouver, ISO, and other styles

29

CHENG, EDDIE, RANDY JIA, and DAVID LU. "MATCHING PRECLUSION AND CONDITIONAL MATCHING PRECLUSION FOR AUGMENTED CUBES." Journal of Interconnection Networks 11, no. 01n02 (March 2010): 35–60. http://dx.doi.org/10.1142/s0219265910002726.

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. For many interconnection networks, the optimal sets are precisely those incident to a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those incident to a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings. In this paper, we find this number and classify all optimal sets for the augmented cubes, a class of networks designed as an improvement of the hypercubes.

APA, Harvard, Vancouver, ISO, and other styles

30

Li, Hong-Hai, and Yi-Ping Liang. "On the k-matchings of the complements of bicyclic graphs." Discrete Mathematics, Algorithms and Applications 10, no. 02 (April 2018): 1850016. http://dx.doi.org/10.1142/s1793830918500167.

Full text

Abstract:

A matching of a graph [Formula: see text] is a set of pairwise nonadjacent edges of [Formula: see text], and a [Formula: see text]-matching is a matching consisting of [Formula: see text] edges. In this paper, we characterize the bicyclic graphs whose complements have the extremal number of [Formula: see text]-matchings for all [Formula: see text].

APA, Harvard, Vancouver, ISO, and other styles

31

Roy, Indradyumna, Venkata Sai Baba Reddy Velugoti, Soumen Chakrabarti, and Abir De. "Interpretable Neural Subgraph Matching for Graph Retrieval." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 7 (June 28, 2022): 8115–23. http://dx.doi.org/10.1609/aaai.v36i7.20784.

Full text

Abstract:

Given a query graph and a database of corpus graphs, a graph retrieval system aims to deliver the most relevant corpus graphs. Graph retrieval based on subgraph matching has a wide variety of applications, e.g., molecular fingerprint detection, circuit design, software analysis, and question answering. In such applications, a corpus graph is relevant to a query graph, if the query graph is (perfectly or approximately) a subgraph of the corpus graph. Existing neural graph retrieval models compare the node or graph embeddings of the query-corpus pairs, to compute the relevance scores between them. However, such models may not provide edge consistency between the query and corpus graphs. Moreover, they predominantly use symmetric relevance scores, which are not appropriate in the context of subgraph matching, since the underlying relevance score in subgraph search should be measured using the partial order induced by subgraph-supergraph relationship. Consequently, they show poor retrieval performance in the context of subgraph matching. In response, we propose ISONET, a novel interpretable neural edge alignment formulation, which is better able to learn the edge-consistent mapping necessary for subgraph matching. ISONET incorporates a new scoring mechanism which enforces an asymmetric relevance score, specifically tailored to subgraph matching. ISONET’s design enables it to directly identify the underlying subgraph in a corpus graph, which is relevant to the given query graph. Our experiments on diverse datasets show that ISONET outperforms recent graph retrieval formulations and systems. Additionally, ISONET can provide interpretable alignments between query-corpus graph pairs during inference, despite being trained only using binary relevance labels of whole graphs during training, without any fine-grained ground truth information about node or edge alignments.

APA, Harvard, Vancouver, ISO, and other styles

32

PANDA, SWARUP. "Inverses of bicyclic graphs." Electronic Journal of Linear Algebra 32 (February 6, 2017): 217–31. http://dx.doi.org/10.13001/1081-3810.3322.

Full text

Abstract:

A graph G is said to be nonsingular (resp., singular) if its adjacency matrix A(G) is nonsingular (resp., singular). The inverse of a nonsingular graph G is the unique weighted graph whose adjacency matrix is similar to the inverse of the adjacency matrix A(G) via a diagonal matrix of Â±1s. Consider connected bipartite graphs with unique perfect matchings such that the graph obtained by contracting all matching edges is also bipartite. In [C.D. Godsil. Inverses of trees. Combinatorica, 5(1):33â39, 1985.], Godsil proved that such graphs are invertible. He posed the question of characterizing the bipartite graphs with unique perfect matchings possessing inverses. In this article, Godsilâs question for the class of bicyclic graphs is answered.

APA, Harvard, Vancouver, ISO, and other styles

33

Nurlanov, Zhakshylyk, Frank R. Schmidt, and Florian Bernard. "Universe Points Representation Learning for Partial Multi-Graph Matching." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 2 (June 26, 2023): 1984–92. http://dx.doi.org/10.1609/aaai.v37i2.25290.

Full text

Abstract:

Many challenges from natural world can be formulated as a graph matching problem. Previous deep learning-based methods mainly consider a full two-graph matching setting. In this work, we study the more general partial matching problem with multi-graph cycle consistency guarantees. Building on a recent progress in deep learning on graphs, we propose a novel data-driven method (URL) for partial multi-graph matching, which uses an object-to-universe formulation and learns latent representations of abstract universe points. The proposed approach advances the state of the art in semantic keypoint matching problem, evaluated on Pascal VOC, CUB, and Willow datasets. Moreover, the set of controlled experiments on a synthetic graph matching dataset demonstrates the scalability of our method to graphs with large number of nodes and its robustness to high partiality.

APA, Harvard, Vancouver, ISO, and other styles

34

Zhang, Chun Ying, Jing Feng Guo, and Xiao Chen. "Research on Random Walk Rough Matching Algorithm of Attribute Sub-Graph." Key Engineering Materials 474-476 (April 2011): 297–302. http://dx.doi.org/10.4028/www.scientific.net/kem.474-476.297.

Full text

Abstract:

In the analysis of social network, the attribute values of an entity change constantly as time goes by and the corresponding attribute graph changes accordingly. However, the essence of the entity is invariable. The problem is how to discover essence from the change of mining frequent rough matching attribute sub-graph in an attribute graph in this paper. The problem of the attribute sub-graph rough matching is defined and described, then the random walk rough matching algorithm of attribute sub-graph is designed so that the problem of incomplete coincide attribute sub-graph rough matching would be solved. Attribute sub-graph is the expansion of the traditional sub-graph; rough matching problem is the extension of traditional sub-graph matching problem. With the help of the random walk rough matching algorithm of attribute sub-graph, more potential frequent attribute sub-graphs can be discovered, and more valuable information mined.

APA, Harvard, Vancouver, ISO, and other styles

35

Koh, Zhuan Khye, and Laura Sanità. "Stabilizing Weighted Graphs." Mathematics of Operations Research 45, no. 4 (November 2020): 1318–41. http://dx.doi.org/10.1287/moor.2019.1034.

Full text

Abstract:

An edge-weighted graph [Formula: see text] is called stable if the value of a maximum-weight matching equals the value of a maximum-weight fractional matching. Stable graphs play an important role in network bargaining games and cooperative matching games, because they characterize instances that admit stable outcomes. We give the first polynomial-time algorithm to find a minimum cardinality subset of vertices whose removal from G yields a stable graph, for any weighted graph G. The algorithm is combinatorial and exploits new structural properties of basic fractional matchings, which are of independent interest. In contrast, we show that the problem of finding a minimum cardinality subset of edges whose removal from a weighted graph G yields a stable graph, does not admit any constant-factor approximation algorithm, unless P = NP. In this setting, we develop an O(Δ)-approximation algorithm for the problem, where Δ is the maximum degree of a node in G.

APA, Harvard, Vancouver, ISO, and other styles

36

Tan, Hao-Ru, Chuang Wang, Si-Tong Wu, Tie-Qiang Wang, Xu-Yao Zhang, and Cheng-Lin Liu. "Proxy Graph Matching with Proximal Matching Networks." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 11 (May 18, 2021): 9808–15. http://dx.doi.org/10.1609/aaai.v35i11.17179.

Full text

Abstract:

Estimating feature point correspondence is a common technique in computer vision. A line of recent data-driven approaches utilizing the graph neural networks improved the matching accuracy by a large margin. However, these learning-based methods require a lot of labeled training data, which are expensive to collect. Moreover, we find most methods are sensitive to global transforms, for example, a random rotation. On the contrary, classical geometric approaches are immune to rotational transformation though their performance is generally inferior. To tackle these issues, we propose a new learning-based matching framework, which is designed to be rotationally invariant. The model only takes geometric information as input. It consists of three parts: a graph neural network to generate a high-level local feature, an attention-based module to normalize the rotational transform, and a global feature matching module based on proximal optimization. To justify our approach, we provide a convergence guarantee for the proximal method for graph matching. The overall performance is validated by numerical experiments. In particular, our approach is trained on the synthetic random graphs and then applied to several real-world datasets. The experimental results demonstrate that our method is robust to rotational transform and highlights its strong performance of matching accuracy.

APA, Harvard, Vancouver, ISO, and other styles

37

V, Jesudas Selvaraj, and Ponnappan C Y. "Perfect Matching in Various Fuzzy Graphs." ECS Transactions 107, no. 1 (April 24, 2022): 19237–51. http://dx.doi.org/10.1149/10701.19237ecst.

Full text

Abstract:

An induced fuzzy sub graph <H> of a fuzzy graph G (V,E) is said to be a matching if every vertex of G (V,E) is incident with at most a vertex in <H>. A induced fuzzy sub graph <H> of a fuzzy graph G (V,E) is said to be a perfect matching if every vertex of G (V,E) is incident with exactly a vertex in <H>. In this paper we will define a perfect matching in fuzzy graphs. Further we investigate the bounds and properties of matching numbers in various fuzzy graphs.

APA, Harvard, Vancouver, ISO, and other styles

38

Yadav, Rohit, François-Xavier Dupé, Sylvain Takerkart, and Guillaume Auzias. "Population-wise labeling of sulcal graphs using multi-graph matching." PLOS ONE 18, no. 11 (November 9, 2023): e0293886. http://dx.doi.org/10.1371/journal.pone.0293886.

Full text

Abstract:

Population-wise matching of the cortical folds is necessary to compute statistics, a required step for e.g. identifying biomarkers of neurological or psychiatric disorders. The difficulty arises from the massive inter-individual variations in the morphology and spatial organization of the folds. The task is challenging both methodologically and conceptually. In the widely used registration-based techniques, these variations are considered as noise and the matching of folds is only implicit. Alternative approaches are based on the extraction and explicit identification of the cortical folds. In particular, representing cortical folding patterns as graphs of sulcal basins—termed sulcal graphs—enables to formalize the task as a graph-matching problem. In this paper, we propose to address the problem of sulcal graph matching directly at the population level using multi-graph matching techniques. First, we motivate the relevance of the multi-graph matching framework in this context. We then present a procedure for generating populations of artificial sulcal graphs, which allows us to benchmark several state-of-the-art multi-graph matching methods. Our results on both artificial and real data demonstrate the effectiveness of multi-graph matching techniques in obtaining a population-wise consistent labeling of cortical folds at the sulcal basin level.

APA, Harvard, Vancouver, ISO, and other styles

39

MAO, YAPING, and EDDIE CHENG. "A Concise Survey of Matching Preclusion in Interconnection Networks." Journal of Interconnection Networks 19, no. 03 (September 2019): 1940006. http://dx.doi.org/10.1142/s0219265919400061.

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. There are other related parameters and generalization including the strong matching preclusion number, the conditional matching preclusion number, the fractional matching preclusion number, and so on. In this survey, we give an introduction on the general topic of matching preclusion.

APA, Harvard, Vancouver, ISO, and other styles

40

Chen, Xiaolin, and Huishu Lian. "Extremal Matching Energy and the Largest Matching Root of Complete Multipartite Graphs." Complexity 2019 (April 16, 2019): 1–7. http://dx.doi.org/10.1155/2019/9728976.

Full text

Abstract:

The matching energy ME(G) of a graph G was introduced by Gutman and Wagner, which is defined as the sum of the absolute values of the roots of the matching polynomial m(G,x). The largest matching root λ1(G) is the largest root of the matching polynomial m(G,x). Let Kn1,n2,…,nr denote the complete r-partite graph with order n=n1+n2+…+nr, where r>1. In this paper, we prove that, for the given values n and r, both the matching energy ME(G) and the largest matching root λ1(G) of complete r-partite graphs are minimal for complete split graph CS(n,r-1) and are maximal for Turán graph T(n,r).

APA, Harvard, Vancouver, ISO, and other styles

41

Farrell, E. J. "Matchings in hexagonal cacti." International Journal of Mathematics and Mathematical Sciences 10, no. 2 (1987): 321–38. http://dx.doi.org/10.1155/s0161171287000395.

Full text

Abstract:

Explicit recurrences are derived for the matching polynomials of the basic types of hexagonal cacti, the linear cactus and the star cactus and also for an associated graph, called the hexagonal crown. Tables of the polynomials are given for each type of graph. Explicit formulae are then obtained for the number of defect-dmatchings in the graphs, for various values ofd. In particular, formulae are derived for the number of perfect matchings in all three types of graphs. Finally, results are given for the total number of matchings in the graphs.

APA, Harvard, Vancouver, ISO, and other styles

42

Yuan, Ling, Jiali Bin, and Peng Pan. "Optimized Distributed Subgraph Matching Algorithm Based on Partition Replication." Electronics 9, no. 1 (January 18, 2020): 184. http://dx.doi.org/10.3390/electronics9010184.

Full text

Abstract:

At present, with the explosive growth of data scale, subgraph matching for massive graph data is difficult to satisfy with efficiency. Meanwhile, the graph index used in existing subgraph matching algorithm is difficult to update and maintain when facing dynamic graphs. We propose a distributed subgraph matching algorithm based on Partition Replica (noted as PR-Match) to process the partition and storage of large-scale data graphs. The PR-Match algorithm first splits the query graph into sub-queries, then assigns the sub-query to each node for sub-graph matching, and finally merges the matching results. In the PR-Match algorithm, we propose a heuristic rule based on prediction cost to select the optimal merging plan, which greatly reduces the cost of merging. In order to accelerate the matching speed of the sub-query graph, a vertex code based on the vertex neighbor label signature is proposed, which greatly reduces the search space for the subquery. As the vertex code is based on the increment, the problem that the feature-based graph index is difficult to maintain in the face of the dynamic graph is solved. An abundance of experiments on real and synthetic datasets demonstrate the high efficiency and strong scalability of the PR-Match algorithm when handling large-scale data graphs.

APA, Harvard, Vancouver, ISO, and other styles

43

Piao, Chengzhi, Tingyang Xu, Xiangguo Sun, Yu Rong, Kangfei Zhao, and Hong Cheng. "Computing Graph Edit Distance via Neural Graph Matching." Proceedings of the VLDB Endowment 16, no. 8 (April 2023): 1817–29. http://dx.doi.org/10.14778/3594512.3594514.

Full text

Abstract:

Graph edit distance (GED) computation is a fundamental NP-hard problem in graph theory. Given a graph pair ( G 1 , G 2 ), GED is defined as the minimum number of primitive operations converting G 1 to G 2 . Early studies focus on search-based inexact algorithms such as A*-beam search, and greedy algorithms using bipartite matching due to its NP-hardness. They can obtain a sub-optimal solution by constructing an edit path (the sequence of operations that converts G 1 to G 2 ). Recent studies convert the GED between a given graph pair ( G 1 , G 2 ) into a similarity score in the range (0, 1) by a well designed function. Then machine learning models (mostly based on graph neural networks) are applied to predict the similarity score. They achieve a much higher numerical precision than the sub-optimal solutions found by classical algorithms. However, a major limitation is that these machine learning models cannot generate an edit path. They treat the GED computation as a pure regression task to bypass its intrinsic complexity, but ignore the essential task of converting G 1 to G 2 . This severely limits the interpretability and usability of the solution. In this paper, we propose a novel deep learning framework that solves the GED problem in a two-step manner: 1) The proposed graph neural network GEDGNN is in charge of predicting the GED value and a matching matrix; and 2) A post-processing algorithm based on k -best matching is used to derive k possible node matchings from the matching matrix generated by GEDGNN. The best matching will finally lead to a high-quality edit path. Extensive experiments are conducted on three real graph data sets and synthetic power-law graphs to demonstrate the effectiveness of our framework. Compared to the best result of existing GNN-based models, the mean absolute error (MAE) on GED value prediction decreases by 4.9% ~ 74.3%. Compared to the state-of-the-art searching algorithm Noah, the MAE on GED value based on edit path reduces by 53.6% ~ 88.1%.

APA, Harvard, Vancouver, ISO, and other styles

44

Rizwan, Muhammad, Akhlaq Ahmad Bhatti, Muhammad Javaid, and Ebenezer Bonyah. "Extremal Values of Variable Sum Exdeg Index for Conjugated Bicyclic Graphs." Journal of Chemistry 2021 (December 10, 2021): 1–11. http://dx.doi.org/10.1155/2021/4272208.

Full text

Abstract:

A connected graph G V , E in which the number of edges is one more than its number of vertices is called a bicyclic graph. A perfect matching of a graph is a matching in which every vertex of the graph is incident to exactly one edge of the matching set such that the number of vertices is two times its matching number. In this paper, we investigated maximum and minimum values of variable sum exdeg index, SEI a for bicyclic graphs with perfect matching for k ≥ 5 and a > 1 .

APA, Harvard, Vancouver, ISO, and other styles

45

Farhadi, Alireza, Jacob Gilbert, and MohammadTaghi Hajiaghayi. "Generalized Stochastic Matching." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 9 (June 28, 2022): 10008–15. http://dx.doi.org/10.1609/aaai.v36i9.21239.

Full text

Abstract:

In this paper, we generalize the recently studied stochastic matching problem to more accurately model a significant medical process, kidney exchange, and several other applications. Up until now the stochastic matching problem that has been studied was as follows: given a graph G= (V,E), each edge is included in the realized sub-graph of G independently with probability pe, and the goal is to find a degree-bounded sub-graph Q of G that has an expected maximum matching that approximates the expected maximum matching of G. This model does not account for possibilities of vertex dropouts, which can be found in several applications, e.g. in kidney exchange when donors or patients opt out of the exchange process as well as in online freelancing and online dating when online profiles are found to be faked. Thus, we will study a more generalized model of stochastic matching in which vertices and edges are both realized independently with some probabilities pv, pe, respectively, which more accurately fits important applications than the previously studied model. We will discuss the first algorithms and analysis for this generalization of the stochastic matching model and prove that they achieve good approximation ratios. In particular, we show that the approximation factor of a natural algorithm for this problem is at least 0.6568 in unweighted graphs, and 1/2+ε in weighted graphs for some constant ε >0. We further improve our result for unweighted graphs to 2/3 using edge degree constrained sub-graphs (EDCS).

APA, Harvard, Vancouver, ISO, and other styles

46

Došlić, Tomislav. "All Pairs of Pentagons in Leapfrog Fullerenes Are Nice." Mathematics 8, no. 12 (December 1, 2020): 2135. http://dx.doi.org/10.3390/math8122135.

Full text

Abstract:

A subgraph H of a graph G with perfect matching is nice if G−V(H) has perfect matching. It is well-known that all fullerene graphs have perfect matchings and that all fullerene graphs contain some small connected graphs as nice subgraphs. In this contribution, we consider fullerene graphs arising from smaller fullerenes via the leapfrog transformation, and show that in such graphs, each pair of (necessarily disjoint) pentagons is nice. That answers in affirmative a question posed in a recent paper on nice pairs of odd cycles in fullerene graphs.

APA, Harvard, Vancouver, ISO, and other styles

47

Terra-Neves, Miguel, José Amaral, Alexandre Lemos, Rui Quintino, Pedro Resende, and Antonio Alegria. "SAT-Based Algorithms for Regular Graph Pattern Matching." Proceedings of the AAAI Conference on Artificial Intelligence 38, no. 8 (March 24, 2024): 8136–45. http://dx.doi.org/10.1609/aaai.v38i8.28653.

Full text

Abstract:

Graph matching is a fundamental problem in pattern recognition, with many applications such as software analysis and computational biology. One well-known type of graph matching problem is graph isomorphism, which consists of deciding if two graphs are identical. Despite its usefulness, the properties that one may check using graph isomorphism are rather limited, since it only allows strict equality checks between two graphs. For example, it does not allow one to check complex structural properties such as if the target graph is an arbitrary length sequence followed by an arbitrary size loop. We propose a generalization of graph isomorphism that allows one to check such properties through a declarative specification. This specification is given in the form of a Regular Graph Pattern (ReGaP), a special type of graph, inspired by regular expressions, that may contain wildcard nodes that represent arbitrary structures such as variable-sized sequences or subgraphs. We propose a SAT-based algorithm for checking if a target graph matches a given ReGaP. We also propose a preprocessing technique for improving the performance of the algorithm and evaluate it through an extensive experimental evaluation on benchmarks from the CodeSearchNet dataset.

APA, Harvard, Vancouver, ISO, and other styles

48

Caetano, T. S., J. J. McAuley, Li Cheng, Q. V. Le, and A. J. Smola. "Learning Graph Matching." IEEE Transactions on Pattern Analysis and Machine Intelligence 31, no. 6 (June 2009): 1048–58. http://dx.doi.org/10.1109/tpami.2009.28.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Zhou, Feng, and Fernando De la Torre. "Factorized Graph Matching." IEEE Transactions on Pattern Analysis and Machine Intelligence 38, no. 9 (September 1, 2016): 1774–89. http://dx.doi.org/10.1109/tpami.2015.2501802.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Fan, Wenfei, Jianzhong Li, Shuai Ma, Nan Tang, Yinghui Wu, and Yunpeng Wu. "Graph pattern matching." Proceedings of the VLDB Endowment 3, no. 1-2 (September 2010): 264–75. http://dx.doi.org/10.14778/1920841.1920878.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Graph matching'

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