%0 Book Section %1 Bunke:2002 %A Bunke, H. %A Foggia, P. %A Guidobaldi, C. %A Sansone, C. %A Vento, M. %B Lecture Notes on Computer Science %C Heidelberg %D 2002 %I Springer-Verlag %K graphs %P 123-132 %T A Comparison of Algorithms for Maximum Common Subgraph on Randomly Connected Graphs %V 2396 %X A graph $g$ is called a maximum common subgraph of two graphs, $g_1$ and $g_2$, if there exists no other common subgraph of $g_1$ and $g_2$ that has more nodes than $g$. For the maximum common subgraph problem, exact and inexact algorithms are known from the literature. Nevertheless, until now no effort has been done for characterizing their performance. In this paper, two exact algorithms for maximum common subgraph detection are described. Moreover a database containing randomly connected pairs of graphs, having a maximum common graph of at least two nodes, is presented, and the performance of the two algorithms is evaluated on this database.

@incollection{Bunke:2002, abstract = {A graph $g$ is called a \emph{maximum common subgraph} of two graphs, $g_1$ and $g_2$, if there exists no other common subgraph of $g_1$ and $g_2$ that has more nodes than $g$. For the maximum common subgraph problem, exact and inexact algorithms are known from the literature. Nevertheless, until now no effort has been done for characterizing their performance. In this paper, two exact algorithms for maximum common subgraph detection are described. Moreover a database containing randomly connected pairs of graphs, having a maximum common graph of at least two nodes, is presented, and the performance of the two algorithms is evaluated on this database.}, added-at = {2007-12-14T02:36:52.000+0100}, address = {Heidelberg}, author = {Bunke, H. and Foggia, P. and Guidobaldi, C. and Sansone, C. and Vento, M.}, biburl = {https://www.bibsonomy.org/bibtex/2cc5b934f613f05a1bed04d07e8a97bea/diego_ma}, booktitle = {Lecture Notes on Computer Science}, interhash = {1a28bc9ebc7aa34e4fc243cfdf4e0d1a}, intrahash = {cc5b934f613f05a1bed04d07e8a97bea}, keywords = {graphs}, pages = {123-132}, publisher = {Springer-Verlag}, timestamp = {2007-12-14T02:36:52.000+0100}, title = {A Comparison of Algorithms for Maximum Common Subgraph on Randomly Connected Graphs}, volume = 2396, year = 2002 }