COIN-OR::LEMON - Graph Library

Changeset 1142:2f479109a71d in lemon-main for doc/groups.dox


Ignore:
Timestamp:
05/14/15 16:07:38 (5 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
Message:

Documentation for VF2 (#597)

The implementation of this feature was sponsored by QuantumBio? Inc.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r1093 r1142  
    562562
    563563/**
     564@defgroup graph_isomorphism Graph Isomorphism
     565@ingroup algs
     566\brief Algorithms for testing (sub)graph isomorphism
     567
     568This group contains algorithms for finding isomorph copies of a
     569given graph in another one, or simply check whether two graphs are isomorphic.
     570
     571The formal definition of subgraph isomorphism is as follows.
     572
     573We are given two graphs, \f$G_1=(V_1,E_1)\f$ and \f$G_2=(V_2,E_2)\f$. A
     574function \f$f:V_1\longrightarrow V_2\f$ is called \e mapping or \e
     575embedding if \f$f(u)\neq f(v)\f$ whenever \f$u\neq v\f$.
     576
     577The standard <em>Subgraph Isomorphism Problem (SIP)</em> looks for a
     578mapping with the property that whenever \f$(u,v)\in E_1\f$, then
     579\f$(f(u),f(v))\in E_2\f$.
     580
     581In case of <em>Induced Subgraph Isomorphism Problem (ISIP)</em> one
     582also requires that if \f$(u,v)\not\in E_1\f$, then \f$(f(u),f(v))\not\in
     583E_2\f$
     584
     585In addition, the graph nodes may be \e labeled, i.e. we are given two
     586node labelings \f$l_1:V_1\longrightarrow L\f$ and \f$l_2:V_2\longrightarrow
     587L\f$ and we require that \f$l_1(u)=l_2(f(u))\f$ holds for all nodes \f$u \in
     588G\f$.
     589
     590*/
     591
     592/**
    564593@defgroup planar Planar Embedding and Drawing
    565594@ingroup algs
Note: See TracChangeset for help on using the changeset viewer.