%% 

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