Name
Abstract | ||
|---|---|---|
In this paper an extension of index-based subgraph matching is proposed. This extension significantly reduces the storage amount and indexing time for graphs where the nodes are labeled with a rather small amount of different classes. In order to reduce the number of possible permutations, a weight function for labeled graphs is introduced and a well-founded total order is defined on the weights of the labels. Inversions which violate the order are not allowed. A computational complexity analysis of the new preprocessing is given and its completeness is proven. Furthermore, in a number of practical experiments with randomly generated graphs the improvement of the new approach is shown. In experiments performed on random sample graphs, the number of permutations has been decreased to a fraction of 10-18 in average compared to the original approach by Messmer. This makes indexing of larger graphs feasible, allowing for fast detection of subgraphs. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-20844-7_19 | GbRPR |
Keywords | Field | DocType |
well-founded total order,small amount,fast detection,subgraph isomorphism detection,indexing time,storage amount,different class,original approach,new approach,computational complexity analysis,new preprocessing,total order,graph isomorphism,random sampling,weight function,computational complexity,indexing,decision tree,subgraph isomorphism,indexation | Discrete mathematics,Combinatorics,Indifference graph,Graph isomorphism,Permutation,Chordal graph,Induced subgraph isomorphism problem,Search engine indexing,Subgraph isomorphism problem,Mathematics,Computational complexity theory | Conference |
Volume | ISSN | Citations |
6658 | 0302-9743 | 3 |
PageRank | References | Authors |
0.38 | 14 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Markus Weber | 1 | 166 | 20.97 |
| Marcus Liwicki | 2 | 1292 | 101.35 |
| Andreas Dengel | 3 | 1926 | 280.42 |