BibSonomy :: BibTeX ::

tag user group author concept BibTeX key search:all search:diego_ma

A blue social bookmark and publication sharing system.

entry of diego_ma: spam

Conceptual Graph Matching: a flexible algorithm and experiments

by: Sung H. Myaeng and Aurelio L\'opez-L\'opez

In: Journal of Experimentation and Theoretical Artificial Intelligence , Vol. 4 (1992) , p. 107-126.

Abstract

Graph matching is recognized as a central problem across a variety of application areas, and application-specific matchers have been developed with different simplifying assumptions to reduce computational complexity. Graph matching is viewed as a form of plausible reasoning when conceptual information contained in graphs are considered, and thus requires an underlying algorithm flexible and general enough to accommodate application-specific matching heuristics and schemes that determine the degree of plausibility. This paper presents such an algorithm, based on the notion of association graphs, developed for matching Sowa's conceptual graphs CG. While the general subgraph isomorphism problem is known to be NP-complete, matching graphs containing conceptual information appears to be computationally tractable. Following the detailed description of the algorithm, some experimental results are shown to discuss the time complexity of the algorithm and its practicability.

BibTeX record

@article{Myaeng:1992,
  author = {Sung H. Myaeng and Aurelio L\'{o}pez-L\'{o}pez},
  interHash = {f7c4070445abf61d9d28d261cdc6d771},
  intraHash = {cede8e16fef190210dab74b1eb62e3f0},
  journal = {Journal of Experimentation and Theoretical Artificial Intelligence},
  pages = {107-126},
  title = {Conceptual Graph Matching: a flexible algorithm and experiments},
  volume = {4},
  year = {1992},
  abstract = {Graph matching is recognized as a central problem across a variety of application areas, and application-specific matchers have been developed with different simplifying assumptions to reduce computational complexity. Graph matching is viewed as a form of plausible reasoning when conceptual information contained in graphs are considered, and thus requires an underlying algorithm flexible and general enough to accommodate application-specific matching heuristics and schemes that determine the degree of plausibility. This paper presents such an algorithm, based on the notion of association graphs, developed for matching Sowa's conceptual graphs (CG). While the general subgraph isomorphism problem is known to be NP-complete, matching graphs containing conceptual information appears to be computationally tractable. Following the detailed description of the algorithm, some experimental results are shown to discuss the time complexity of the algorithm and its practicability.}
}

Endnote record

%0 Journal Article
%1 Myaeng:1992
%A Sung H. Myaeng
%A Aurelio L\'{o}pez-L\'{o}pez
%D 1992
%J Journal of Experimentation and Theoretical Artificial Intelligence
%K 
%P 107-126
%T Conceptual Graph Matching: a flexible algorithm and experiments
%V 4
%X Graph matching is recognized as a central problem across a variety of application areas, and application-specific matchers have been developed with different simplifying assumptions to reduce computational complexity. Graph matching is viewed as a form of plausible reasoning when conceptual information contained in graphs are considered, and thus requires an underlying algorithm flexible and general enough to accommodate application-specific matching heuristics and schemes that determine the degree of plausibility. This paper presents such an algorithm, based on the notion of association graphs, developed for matching Sowa's conceptual graphs (CG). While the general subgraph isomorphism problem is known to be NP-complete, matching graphs containing conceptual information appears to be computationally tractable. Following the detailed description of the algorithm, some experimental results are shown to discuss the time complexity of the algorithm and its practicability.