Paper Info
Title
Using graph distance in object recognition
Abstract
In this paper the concept of the distance between graphs is applied to the problem of recognizing objects. An unknown object is represented by a graph H and from the data base of possible solutions {G1, …, Gn} (also graphs) we select the graph Gi for which the distance to H is the smallest. The graph Gi is the recognition of H. The distance between graphs is defined in terms of edge rotation and deletion. It is shown that this distance defines a metric on the space of all graphs. The bounds for distance between two graphs are given in terms of their sizes and the size of their greatest common subgraph. It is proved that finding a distance between two graphs is an NP-complete problem even for planar graphs. An algorithm based on exhaustive search utilizing the linear algorithm by Hopcroft and Wong for recognizing isomorphism of planar graphs with some stopping criteria to maintain polynomial complexity, is possible.
Year
DOI
Venue
1990
10.1145/100348.100355
ACM Conference on Computer Science
Keywords
DocType
ISBN
object recognition,data base,possible solution,exhaustive search,greatest common subgraph,edge rotation,planar graph,np-complete problem,graph h,graph distance,graph gi,linear algorithm,np complete problem
Conference
0-89791-348-5
Citations 
PageRank 
References 
16
0.88
4
Authors
3
Name
Order
Citations
PageRank
Ewa Kubicka1669.61
Grzegorz Kubicki29515.16
Ignatios Vakalis3254.24