| Autor: |
Grzegorz Kubicki, Ignatios E. Vakalis, Ewa Kubicka |
| Rok vydání: |
1990 |
| Předmět: |
|
| Zdroj: |
ACM Conference on Computer Science |
| Popis: |
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. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
