## Abstract

We consider the problem of comparison between labeled graphs. The criterion for comparison is the distance as measured by a weighted sum of the costs of deletion, in-sertion, and relabel operations on graph nodes and edges. Specifically, we consider two variants of the approximate graph matching problem: Given a pattern graph P and a data graph D, what is the distance between P and D ? What is the minimum distance between P and D when subgraphs can be freely removed from D ? We first observe that no efficient algorithm can solve either variant of the problem, unless P = NP. Then we present several heuristic algorithms based on probabilistic hill climbing techniques. Finally we evaluate the accuracy and time efficiency of the heuristics by applying them to a set of generated graphs and DNA molecules.

Original language | English (US) |
---|---|

Pages (from-to) | 390-396 |

Number of pages | 7 |

Journal | Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI |

DOIs | |

State | Published - 1994 |

Event | Proceedings of the 6th International Conference on Tools with Artificial Intelligence - New Orleans, LA, USA Duration: Nov 6 1994 → Nov 9 1994 |

## All Science Journal Classification (ASJC) codes

- Software
- Artificial Intelligence
- Computer Science Applications