Algorithms for approximate graph matching

Jason T.L. Wang, Kaizhong Zhang, Gung Wei Chirn

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

Abstract

Labeled graphs are graphs in which each node and edge has a label. The distance between two labeled graphs is considered to be the weighted sum of the costs of edit operations (insert, delete, and relabel the nodes and edges) to transform one graph to the other. The paper considers two variants of the approximate graph matching problem (AGM): Given a pattern graph P and a data graph D: 1. 1. What is the distance between P and D? 2. 2. What is the minimum distance between P and D when subgraphs can be freely removed from D? We first show that no efficient algorithm can solve either variant of the AGM unless P = NP. Then we present several heuristic algorithms leading to approximate solutions. The heuristics are based on probabilistic hill climbing and maximum flow techniques. Our experimental results involving the comparison of real and simulated data demonstrate the good performance of the algorithms presented.

Original languageEnglish (US)
Pages (from-to)45-74
Number of pages30
JournalInformation sciences
Volume82
Issue number1-2
DOIs
StatePublished - Jan 1995

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Algorithms for approximate graph matching'. Together they form a unique fingerprint.

Cite this