alpar@0: %% 
alpar@0: %% Copyright 2007, 2008, 2009 Elsevier Ltd
alpar@0: %% 
alpar@0: %% This file is part of the 'Elsarticle Bundle'.
alpar@0: %% ---------------------------------------------
alpar@0: %% 
alpar@0: %% It may be distributed under the conditions of the LaTeX Project Public
alpar@0: %% License, either version 1.2 of this license or (at your option) any
alpar@0: %% later version.  The latest version of this license is in
alpar@0: %%    http://www.latex-project.org/lppl.txt
alpar@0: %% and version 1.2 or later is part of all distributions of LaTeX
alpar@0: %% version 1999/12/01 or later.
alpar@0: %% 
alpar@0: %% The list of all files belonging to the 'Elsarticle Bundle' is
alpar@0: %% given in the file `manifest.txt'.
alpar@0: %% 
alpar@0: 
alpar@0: %% Template article for Elsevier's document class `elsarticle'
alpar@0: %% with numbered style bibliographic references
alpar@0: %% SP 2008/03/01
alpar@0: 
alpar@0: \documentclass[preprint,12pt]{elsarticle}
alpar@0: 
alpar@0: %% Use the option review to obtain double line spacing
alpar@0: %% \documentclass[authoryear,preprint,review,12pt]{elsarticle}
alpar@0: 
alpar@0: %% Use the options 1p,twocolumn; 3p; 3p,twocolumn; 5p; or 5p,twocolumn
alpar@0: %% for a journal layout:
alpar@0: %% \documentclass[final,1p,times]{elsarticle}
alpar@0: %% \documentclass[final,1p,times,twocolumn]{elsarticle}
alpar@0: %% \documentclass[final,3p,times]{elsarticle}
alpar@0: %% \documentclass[final,3p,times,twocolumn]{elsarticle}
alpar@0: %% \documentclass[final,5p,times]{elsarticle}
alpar@0: %% \documentclass[final,5p,times,twocolumn]{elsarticle}
alpar@0: 
alpar@0: %% For including figures, graphicx.sty has been loaded in
alpar@0: %% elsarticle.cls. If you prefer to use the old commands
alpar@0: %% please give \usepackage{epsfig}
alpar@0: 
alpar@0: %% The amssymb package provides various useful mathematical symbols
alpar@0: \usepackage{amssymb}
alpar@0: %% The amsthm package provides extended theorem environments
alpar@0: %% \usepackage{amsthm}
alpar@0: 
alpar@0: %% The lineno packages adds line numbers. Start line numbering with
alpar@0: %% \begin{linenumbers}, end it with \end{linenumbers}. Or switch it on
alpar@0: %% for the whole article with \linenumbers.
alpar@0: %% \usepackage{lineno}
alpar@0: 
alpar@1: \journal{Discrete Applied Mathematics}
alpar@0: 
alpar@0: \begin{document}
alpar@0: 
alpar@0: \begin{frontmatter}
alpar@0: 
alpar@0: %% Title, authors and addresses
alpar@0: 
alpar@0: %% use the tnoteref command within \title for footnotes;
alpar@0: %% use the tnotetext command for theassociated footnote;
alpar@0: %% use the fnref command within \author or \address for footnotes;
alpar@0: %% use the fntext command for theassociated footnote;
alpar@0: %% use the corref command within \author for corresponding author footnotes;
alpar@0: %% use the cortext command for theassociated footnote;
alpar@0: %% use the ead command for the email address,
alpar@0: %% and the form \ead[url] for the home page:
alpar@0: %% \title{Title\tnoteref{label1}}
alpar@0: %% \tnotetext[label1]{}
alpar@0: %% \author{Name\corref{cor1}\fnref{label2}}
alpar@0: %% \ead{email address}
alpar@0: %% \ead[url]{home page}
alpar@0: %% \fntext[label2]{}
alpar@0: %% \cortext[cor1]{}
alpar@0: %% \address{Address\fnref{label3}}
alpar@0: %% \fntext[label3]{}
alpar@0: 
alpar@1: \title{Improved Algorithms for Matching Biological Graphs}
alpar@0: 
alpar@0: %% use optional labels to link authors explicitly to addresses:
alpar@0: %% \author[label1,label2]{}
alpar@0: %% \address[label1]{}
alpar@0: %% \address[label2]{}
alpar@0: 
alpar@1: \author{Alp{\'a}r J{\"u}ttner and P{\'e}ter Madarasi}
alpar@0: 
alpar@1: \address{Dept of Operations Research, ELTE}
alpar@0: 
alpar@0: \begin{abstract}
alpar@1: Subgraph isomorphism is a well-known NP-Complete problem, while its
alpar@1: special case, the graph isomorphism problem is one of the few problems
alpar@1: in NP neither known to be in P nor NP-Complete. Their appearance in
alpar@1: many fields of application such as pattern analysis, computer vision
alpar@1: questions and the analysis of chemical and biological systems has
alpar@1: fostered the design of various algorithms for handling special graph
alpar@1: structures.
alpar@0: 
alpar@1: The idea of using state space representation and checking some
alpar@1: conditions in each state to prune the search tree has made the VF2
alpar@1: algorithm one of the state of the art graph matching algorithms for
alpar@1: more than a decade. Recently, biological questions of ever increasing
alpar@1: importance have required more efficient, specialized algorithms.
alpar@1: 
alpar@1: This paper presents VF2++, a new algorithm based on the original VF2,
alpar@1: which runs significantly faster on most test cases and performs
alpar@1: especially well on special graph classes stemming from biological
alpar@1: questions. VF2++ handles graphs of thousands of nodes in practically
alpar@1: near linear time including preprocessing. Not only is it an improved
alpar@1: version of VF2, but in fact, it is by far the fastest existing
alpar@1: algorithm regarding biological graphs.
alpar@1: 
alpar@1: The reason for VF2++' superiority over VF2 is twofold. Firstly, taking
alpar@1: into account the structure and the node labeling of the graph, VF2++
alpar@1: determines a state order in which most of the unfruitful branches of
alpar@1: the search space can be pruned immediately. Secondly, introducing more
alpar@1: efficient - nevertheless still easier to compute - cutting rules
alpar@1: reduces the chance of going astray even further.
alpar@1: 
alpar@1: In addition to the usual subgraph isomorphism, specialized versions
alpar@1: for induced subgraph isomorphism and for graph isomorphism are
alpar@1: presented. VF2++ has gained a runtime improvement of one order of
alpar@1: magnitude respecting induced subgraph isomorphism and a better
alpar@1: asymptotical behaviour in the case of graph isomorphism problem.
alpar@1: 
alpar@1: After having provided the description of VF2++, in order to evaluate
alpar@1: its effectiveness, an extensive comparison to the contemporary other
alpar@1: algorithms is shown, using a wide range of inputs, including both real
alpar@1: life biological and chemical datasets and standard randomly generated
alpar@1: graph series.
alpar@1: 
alpar@1: The work was motivated and sponsored by QuantumBio Inc., and all the
alpar@1: developed algorithms are available as the part of the open source
alpar@1: LEMON graph and network optimization library
alpar@1: (http://lemon.cs.elte.hu).
alpar@0: \end{abstract}
alpar@0: 
alpar@0: \begin{keyword}
alpar@0: %% keywords here, in the form: keyword \sep keyword
alpar@0: 
alpar@0: %% PACS codes here, in the form: \PACS code \sep code
alpar@0: 
alpar@0: %% MSC codes here, in the form: \MSC code \sep code
alpar@0: %% or \MSC[2008] code \sep code (2000 is the default)
alpar@0: 
alpar@0: \end{keyword}
alpar@0: 
alpar@0: \end{frontmatter}
alpar@0: 
alpar@0: %% \linenumbers
alpar@0: 
alpar@0: %% main text
alpar@0: \section{}
alpar@0: \label{}
alpar@0: 
alpar@0: %% The Appendices part is started with the command \appendix;
alpar@0: %% appendix sections are then done as normal sections
alpar@0: %% \appendix
alpar@0: 
alpar@0: %% \section{}
alpar@0: %% \label{}
alpar@0: 
alpar@0: %% If you have bibdatabase file and want bibtex to generate the
alpar@0: %% bibitems, please use
alpar@0: %%
alpar@0: %%  \bibliographystyle{elsarticle-num} 
alpar@0: %%  \bibliography{<your bibdatabase>}
alpar@0: 
alpar@0: %% else use the following coding to input the bibitems directly in the
alpar@0: %% TeX file.
alpar@0: 
alpar@0: \begin{thebibliography}{00}
alpar@0: 
alpar@0: %% \bibitem{label}
alpar@0: %% Text of bibliographic item
alpar@0: 
alpar@0: \bibitem{}
alpar@0: 
alpar@0: \end{thebibliography}
alpar@0: \end{document}
alpar@0: \endinput
alpar@0: %%
alpar@0: %% End of file `elsarticle-template-num.tex'.