Structural Graph Matching With Polynomial Bounds On Memory and On Worst-Case Effort

Fred W. DePiero, California Polytechnic State University - San Luis Obispo

Article comments

DOI: http://dx.doi.org/10.1109/ICPR.2004.1334546.

© 2004 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

Abstract

A new method of structural graph matching is introduced and compared against an existing method and against the maximum common subgraph. The method is approximate with polynomial bounds on both memory and on the worst-case compute effort. Methods work on arbitrary types of graphs and tests with strongly regular graphs are included. No node or edge colors are needed in the methods; the common subgraph is extracted based in structural comparisons only. Monte Carlo trials are benchmarked with 100% additional (clutter) nodes. Results are shown to be typically within 1-2 nodes of the maximum common subgraph. Over 7500 test trials are reported with graphs up to 100 nodes.