%% 

 %% Copyright 2007, 2008, 2009 Elsevier Ltd

 %% 

 %% This file is part of the 'Elsarticle Bundle'.

 %% ---------------------------------------------

 %% 

 %% It may be distributed under the conditions of the LaTeX Project Public

 %% License, either version 1.2 of this license or (at your option) any

 %% later version.  The latest version of this license is in

 %%    http://www.latex-project.org/lppl.txt

 %% and version 1.2 or later is part of all distributions of LaTeX

 %% version 1999/12/01 or later.

 %% 

 %% The list of all files belonging to the 'Elsarticle Bundle' is

 %% given in the file `manifest.txt'.

 %% 

 %% Template article for Elsevier's document class `elsarticle'

 %% with numbered style bibliographic references

 %% SP 2008/03/01

 \documentclass[preprint,12pt]{elsarticle}

 %% Use the option review to obtain double line spacing

 %% \documentclass[authoryear,preprint,review,12pt]{elsarticle}

 %% Use the options 1p,twocolumn; 3p; 3p,twocolumn; 5p; or 5p,twocolumn

 %% for a journal layout:

 %% \documentclass[final,1p,times]{elsarticle}

 %% \documentclass[final,1p,times,twocolumn]{elsarticle}

 %% \documentclass[final,3p,times]{elsarticle}

 %% \documentclass[final,3p,times,twocolumn]{elsarticle}

 %% \documentclass[final,5p,times]{elsarticle}

 %% \documentclass[final,5p,times,twocolumn]{elsarticle}

 %% For including figures, graphicx.sty has been loaded in

 %% elsarticle.cls. If you prefer to use the old commands

 %% please give \usepackage{epsfig}

 %% The amssymb package provides various useful mathematical symbols

 \usepackage{amssymb}

 %% The amsthm package provides extended theorem environments

 %% \usepackage{amsthm}

 %% The lineno packages adds line numbers. Start line numbering with

 %% \begin{linenumbers}, end it with \end{linenumbers}. Or switch it on

 %% for the whole article with \linenumbers.

 %% \usepackage{lineno}

 \journal{Discrete Applied Mathematics}

 \begin{document}

 \begin{frontmatter}

 %% Title, authors and addresses

 %% use the tnoteref command within \title for footnotes;

 %% use the tnotetext command for theassociated footnote;

 %% use the fnref command within \author or \address for footnotes;

 %% use the fntext command for theassociated footnote;

 %% use the corref command within \author for corresponding author footnotes;

 %% use the cortext command for theassociated footnote;

 %% use the ead command for the email address,

 %% and the form \ead[url] for the home page:

 %% \title{Title\tnoteref{label1}}

 %% \tnotetext[label1]{}

 %% \author{Name\corref{cor1}\fnref{label2}}

 %% \ead{email address}

 %% \ead[url]{home page}

 %% \fntext[label2]{}

 %% \cortext[cor1]{}

 %% \address{Address\fnref{label3}}

 %% \fntext[label3]{}

 \title{Improved Algorithms for Matching Biological Graphs}

 %% use optional labels to link authors explicitly to addresses:

 %% \author[label1,label2]{}

 %% \address[label1]{}

 %% \address[label2]{}

 \author{Alp{\'a}r J{\"u}ttner and P{\'e}ter Madarasi}

 \address{Dept of Operations Research, ELTE}

 \begin{abstract}

 Subgraph isomorphism is a well-known NP-Complete problem, while its

 special case, the graph isomorphism problem is one of the few problems

 in NP neither known to be in P nor NP-Complete. Their appearance in

 many fields of application such as pattern analysis, computer vision

 questions and the analysis of chemical and biological systems has

 fostered the design of various algorithms for handling special graph

 structures.

 The idea of using state space representation and checking some

 conditions in each state to prune the search tree has made the VF2

 algorithm one of the state of the art graph matching algorithms for

 more than a decade. Recently, biological questions of ever increasing

 importance have required more efficient, specialized algorithms.

 This paper presents VF2++, a new algorithm based on the original VF2,

 which runs significantly faster on most test cases and performs

 especially well on special graph classes stemming from biological

 questions. VF2++ handles graphs of thousands of nodes in practically

 near linear time including preprocessing. Not only is it an improved

 version of VF2, but in fact, it is by far the fastest existing

 algorithm regarding biological graphs.

 The reason for VF2++' superiority over VF2 is twofold. Firstly, taking

 into account the structure and the node labeling of the graph, VF2++

 determines a state order in which most of the unfruitful branches of

 the search space can be pruned immediately. Secondly, introducing more

 efficient - nevertheless still easier to compute - cutting rules

 reduces the chance of going astray even further.

 In addition to the usual subgraph isomorphism, specialized versions

 for induced subgraph isomorphism and for graph isomorphism are

 presented. VF2++ has gained a runtime improvement of one order of

 magnitude respecting induced subgraph isomorphism and a better

 asymptotical behaviour in the case of graph isomorphism problem.

 After having provided the description of VF2++, in order to evaluate

 its effectiveness, an extensive comparison to the contemporary other

 algorithms is shown, using a wide range of inputs, including both real

 life biological and chemical datasets and standard randomly generated

 graph series.

 The work was motivated and sponsored by QuantumBio Inc., and all the

 developed algorithms are available as the part of the open source

 LEMON graph and network optimization library

 (http://lemon.cs.elte.hu).

 \end{abstract}

 \begin{keyword}

 %% keywords here, in the form: keyword \sep keyword

 %% PACS codes here, in the form: \PACS code \sep code

 %% MSC codes here, in the form: \MSC code \sep code

 %% or \MSC[2008] code \sep code (2000 is the default)

 \end{keyword}

 \end{frontmatter}

 %% \linenumbers

 %% main text

 \section{}

 \label{}

 %% The Appendices part is started with the command \appendix;

 %% appendix sections are then done as normal sections

 %% \appendix

 %% \section{}

 %% \label{}

 %% If you have bibdatabase file and want bibtex to generate the

 %% bibitems, please use

 %%

 %%  \bibliographystyle{elsarticle-num} 

 %%  \bibliography{<your bibdatabase>}

 %% else use the following coding to input the bibitems directly in the

 %% TeX file.

 \begin{thebibliography}{00}

 %% \bibitem{label}

 %% Text of bibliographic item

 \bibitem{}

 \end{thebibliography}

 \end{document}

 \endinput

 %%

 %% End of file `elsarticle-template-num.tex'.