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
It is still an open question whether the graph isomorphism problem belongs to the NP class or not. Polynomial algorithms have been developed for special classes of graphs such as bounded valence graphs [23] (i.e., graphs where the maximum number of edges adjacent to a node is bounded by a constant); planar graphs [24] (i.e., graphs that can be drawn on a plane without graph edges crossing) and trees [11] (i.e., graphs with no cycles). But no polynomial algorithms are known for the general case. Conversely, the subgraph isomorphism problem is proven to be NP-complete [25].
Structure and Representation
Published in Jonathan L. Gross, Jay Yellen, Mark Anderson, Graph Theory and Its Applications, 2018
Jonathan L. Gross, Jay Yellen, Mark Anderson
Two different-seeming graph representations might actually be alternative descriptions of structurally equivalent graphs. Developing a universally applicable method for deciding structural equivalence is called the graph isomorphism problem. Although the analogous problem for vector spaces reduces simply to checking if the dimensions are equal, no such simple test is available in graph theory. Some strategies and tests work well in many instances, but no one has developed a practical method to handle all cases.
A general system for heuristic minimization of convex functions over non-convex sets
Published in Optimization Methods and Software, 2018
S. Diamond, R. Takapoui, S. Boyd
Since in practical applications isomorphic graphs might be contaminated by noise, the inexact graph isomorphism problem is usually stated [1,17,84], in which we want to find a permutation matrix Z such that the disagreement between the transformed matrix and the target matrix is minimized. Solving inexact graph isomorphism problems is of interest in pattern recognition [15,69], computer vision [71], shape analysis [39,73], image and video indexing [55], and neuroscience [86]. In many of the aforementioned fields graphs are used to represent geometric structures, and can be interpreted as the strength of geometric deformation.