Abstract | ||
---|---|---|
This work presents an algorithm for the sub-graph isomorphism problem based on a new pruning technique for directed graphs. During the tree search, the method checks if a new association between two vertices is compatible by considering the structure of their local neighborhoods, represented as the number of limited-length paths of different type originating from each vertex. In addition, randomized versions of the algorithms are studied experimentally by deriving their runtime distributions. Finally, algorithm portfolios consisting of multiple instances of the same randomized algorithm are proposed and analyzed. The experimental results on benchmark graphs demonstrate that the new pruning method is competitive w.r.t. recently proposed techniques. Significantly better results are obtained on sparse graphs. Furthermore, even better results are obtained by the portfolios, when both the average and standard deviation of solution times are considered. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1007/978-3-540-74446-7_8 | SLS |
Keywords | Field | DocType |
randomized version,randomized algorithm,competitive w,new association,better result,benchmark graph,method check,algorithm portfolio,sub-graph isomorphism problem,new pruning technique,new pruning method,standard deviation,graph isomorphism,directed graph | Randomized algorithm,Graph isomorphism,Vertex (geometry),Graph homomorphism,Algorithm,Directed graph,Hopcroft–Karp algorithm,Isomorphism,Mathematics,Graph isomorphism problem | Conference |
Volume | ISSN | Citations |
4638 | 0302-9743 | 4 |
PageRank | References | Authors |
0.49 | 6 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Roberto Battiti | 1 | 1937 | 262.40 |
Franco Mascia | 2 | 96 | 7.24 |