%% 
%% 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'.
