Matching graphs with unique node labels
Autor: | Miro Kraetzl, Horst Bunke, Arek Dadej, Peter Dickinson |
---|---|
Přispěvatelé: | Dadej, Arkadiusz Jan, Dickinson, Peter, Bunke, Horst, Kraetzl, Miro |
Rok vydání: | 2004 |
Předmět: |
Discrete mathematics
Subgraph isomorphism problem Combinatorics Indifference graph Pathwidth Artificial Intelligence Chordal graph Maximal independent set Induced subgraph isomorphism problem Cograph Computer Vision and Pattern Recognition Graph isomorphism MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
Zdroj: | Pattern Analysis and Applications. 7:243-254 |
ISSN: | 1433-755X 1433-7541 |
Popis: | A special class of graphs is introduced in this paper. The graphs belonging to this class are characterised by the existence of unique node labels. A number of matching algorithms for graphs with unique node labels are developed. It is shown that problems such as graph isomorphism, subgraph isomorphism, maximum common subgraph (MCS) and graph edit distance (GED) have a computational complexity that is only quadratic in the number of nodes. Moreover, computing the median of a set of graphs is only linear in the cardinality of the set. In a series of experiments, it is demonstrated that the proposed algorithms run very fast in practice. The considered class makes the matching of large graphs, consisting of thousands of nodes, computationally tractable. We also discuss an application of the considered class of graphs and related matching algorithms to the classification and detection of abnormal events in computer networks. |
Databáze: | OpenAIRE |
Externí odkaz: |