China 
Africa 
Explore chapters and articles related to this topic
Graph Edit Distance—Theory, Algorithms, and Applications
Published in Olivier Lézoray, Leo Grady, Image Processing and Analysis with Graphs, 2012
One of the most important algorithms based on this approach is described in [15]. It addresses both the graph and subgraph isomorphism problem. To prune unfruitful paths at an early stage, the author proposes a refinement procedure that drops pairs of nodes that are inconsistent with the partial match being explored. The branches of this partial match leading to these incompatible matches are not expanded. A similar strategy is used in [18], where the authors include an additional preprocessing step that creates an initial partition of the nodes of the graph based on a distance matrix to reduce the size of the search space. More recent approaches are the VF [19] and the VF2 [20] algorithms. In these works, the authors define a heuristic based on the analysis of the nodes adjacent to the nodes of the partial mapping. This procedure is fast to compute and leads in many cases to an improvement over the approach of [15]. Another recent approach which combines explicit search in state-space and the use of energy minimization is [21]. The basic heuristic of this algorithm can be interpreted as a greedy algorithm to form maximal cliques in an association graph. In addition, the authors allow for vertex swaps during the clique creation. This last characteristic makes this algorithm faster than a PBH (pivoting-based heuristic).
Mobile 3D assembly process information construction and transfer to the assembly station of complex products
Published in International Journal of Computer Integrated Manufacturing, 2018
Hong Xiao, Yugang Duan, Zhongbo Zhang
The constraint satisfaction problem (CSP) is expressed as , where is the variable set; contains the respective domains for the variables in ; and should be subject to the constraint set (van Hoeve 2001). Zampelli, Deville, and Solnon (2010) formulated the subgraph isomorphism problem as CSP, i.e. variable is associated with every node of the pattern graph , and its domain is the node set of target graph ; this CSP should meet the AllDiff constraint, which indicates that all variables must be pairwise different.