TY - GEN
T1 - Solving graph isomorphism using parameterized matching
AU - Mendivelso, Juan
AU - Kim, Sunghwan
AU - Elnikety, Sameh
AU - He, Yuxiong
AU - Hwang, Seung Won
AU - Pinzón, Yoan
PY - 2013
Y1 - 2013
N2 - We propose a new approach to solve graph isomorphism using parameterized matching. To find isomorphism between two graphs, one graph is linearized, i.e. , represented as a graph walk that covers all nodes and edges such that each element is represented by a parameter. Next, we match the graph linearization on the second graph, searching for a bijective function that maps each element of the first graph to an element of the second graph. We develop an efficient linearization algorithm that generates short linearization with an approximation guarantee, and develop a graph matching algorithm. We evaluate our approach experimentally on graphs of different types and sizes, and compare to the performance of VF2, which is a prominent algorithm for graph isomorphism. Our empirical measurements show that graph linearization finds a matching graph faster than VF2 in many cases because of better pruning of the search space.
AB - We propose a new approach to solve graph isomorphism using parameterized matching. To find isomorphism between two graphs, one graph is linearized, i.e. , represented as a graph walk that covers all nodes and edges such that each element is represented by a parameter. Next, we match the graph linearization on the second graph, searching for a bijective function that maps each element of the first graph to an element of the second graph. We develop an efficient linearization algorithm that generates short linearization with an approximation guarantee, and develop a graph matching algorithm. We evaluate our approach experimentally on graphs of different types and sizes, and compare to the performance of VF2, which is a prominent algorithm for graph isomorphism. Our empirical measurements show that graph linearization finds a matching graph faster than VF2 in many cases because of better pruning of the search space.
UR - http://www.scopus.com/inward/record.url?scp=84893933217&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893933217&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-02432-5_26
DO - 10.1007/978-3-319-02432-5_26
M3 - Conference contribution
AN - SCOPUS:84893933217
SN - 9783319024318
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 230
EP - 242
BT - String Processing and Information Retrieval - 20th International Symposium, SPIRE 2013, Proceedings
PB - Springer Verlag
T2 - 20th International Symposium on String Processing and Information Retrieval, SPIRE 2013
Y2 - 7 October 2013 through 9 October 2013
ER -