1.1 --- a/damecco.tex	Fri Nov 18 16:18:02 2016 +0100
     1.2 +++ b/damecco.tex	Fri Nov 18 16:45:03 2016 +0100
     1.3 @@ -47,7 +47,7 @@
     1.4  %% for the whole article with \linenumbers.
     1.5  %% \usepackage{lineno}
     1.6  
     1.7 -\journal{Nuclear Physics B}
     1.8 +\journal{Discrete Applied Mathematics}
     1.9  
    1.10  \begin{document}
    1.11  
    1.12 @@ -73,20 +73,63 @@
    1.13  %% \address{Address\fnref{label3}}
    1.14  %% \fntext[label3]{}
    1.15  
    1.16 -\title{}
    1.17 +\title{Improved Algorithms for Matching Biological Graphs}
    1.18  
    1.19  %% use optional labels to link authors explicitly to addresses:
    1.20  %% \author[label1,label2]{}
    1.21  %% \address[label1]{}
    1.22  %% \address[label2]{}
    1.23  
    1.24 -\author{}
    1.25 +\author{Alp{\'a}r J{\"u}ttner and P{\'e}ter Madarasi}
    1.26  
    1.27 -\address{}
    1.28 +\address{Dept of Operations Research, ELTE}
    1.29  
    1.30  \begin{abstract}
    1.31 -%% Text of abstract
    1.32 +Subgraph isomorphism is a well-known NP-Complete problem, while its
    1.33 +special case, the graph isomorphism problem is one of the few problems
    1.34 +in NP neither known to be in P nor NP-Complete. Their appearance in
    1.35 +many fields of application such as pattern analysis, computer vision
    1.36 +questions and the analysis of chemical and biological systems has
    1.37 +fostered the design of various algorithms for handling special graph
    1.38 +structures.
    1.39  
    1.40 +The idea of using state space representation and checking some
    1.41 +conditions in each state to prune the search tree has made the VF2
    1.42 +algorithm one of the state of the art graph matching algorithms for
    1.43 +more than a decade. Recently, biological questions of ever increasing
    1.44 +importance have required more efficient, specialized algorithms.
    1.45 +
    1.46 +This paper presents VF2++, a new algorithm based on the original VF2,
    1.47 +which runs significantly faster on most test cases and performs
    1.48 +especially well on special graph classes stemming from biological
    1.49 +questions. VF2++ handles graphs of thousands of nodes in practically
    1.50 +near linear time including preprocessing. Not only is it an improved
    1.51 +version of VF2, but in fact, it is by far the fastest existing
    1.52 +algorithm regarding biological graphs.
    1.53 +
    1.54 +The reason for VF2++' superiority over VF2 is twofold. Firstly, taking
    1.55 +into account the structure and the node labeling of the graph, VF2++
    1.56 +determines a state order in which most of the unfruitful branches of
    1.57 +the search space can be pruned immediately. Secondly, introducing more
    1.58 +efficient - nevertheless still easier to compute - cutting rules
    1.59 +reduces the chance of going astray even further.
    1.60 +
    1.61 +In addition to the usual subgraph isomorphism, specialized versions
    1.62 +for induced subgraph isomorphism and for graph isomorphism are
    1.63 +presented. VF2++ has gained a runtime improvement of one order of
    1.64 +magnitude respecting induced subgraph isomorphism and a better
    1.65 +asymptotical behaviour in the case of graph isomorphism problem.
    1.66 +
    1.67 +After having provided the description of VF2++, in order to evaluate
    1.68 +its effectiveness, an extensive comparison to the contemporary other
    1.69 +algorithms is shown, using a wide range of inputs, including both real
    1.70 +life biological and chemical datasets and standard randomly generated
    1.71 +graph series.
    1.72 +
    1.73 +The work was motivated and sponsored by QuantumBio Inc., and all the
    1.74 +developed algorithms are available as the part of the open source
    1.75 +LEMON graph and network optimization library
    1.76 +(http://lemon.cs.elte.hu).
    1.77  \end{abstract}
    1.78  
    1.79  \begin{keyword}