@Article{bahiense12maximum,
  author    = {Laura Bahiense and Gordana Mani\'c and Breno Piva and Cid C. de Souza},
  title     = {The maximum common edge subgraph problem: A polyhedral investigation},
  journal   = {Discrete Appl Math},
  year      = {2012},
  volume    = {160},
  number    = {18},
  pages     = {2523 - 2541},
  abstract  = {In the Maximum Common Edge Subgraph Problem (MCES), given two graphs G and H with the same number of vertices, one has to find a common subgraph of G and H (not necessarily induced) with the maximum number of edges. This problem arises in parallel programming environments, and was first defined in?Bokhari (1981) [2]. This paper presents a new integer programming formulation for the MCES and a polyhedral study of this model. Several classes of valid inequalities are identified, most of which are shown to define facets. These findings were incorporated into a branch&cut algorithm we implemented. Experimental results with this algorithm are reported.},
  doi       = {10.1016/j.dam.2012.01.026},
  keywords  = {Maximum common subgraph problem, Graph isomorphism, Polyhedral combinatorics, Branch&cut algorithm},
  owner     = {Sebastian},
  timestamp = {2019.08.04},
}

{"_id":"dY9d49HcHA4iqmMrj","bibbaseid":"bahiense-mani-piva-desouza-themaximumcommonedgesubgraphproblemapolyhedralinvestigation-2012","authorIDs":[],"author_short":["Bahiense, L.","Manić, G.","Piva, B.","de Souza, C. C."],"bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["Laura"],"propositions":[],"lastnames":["Bahiense"],"suffixes":[]},{"firstnames":["Gordana"],"propositions":[],"lastnames":["Manić"],"suffixes":[]},{"firstnames":["Breno"],"propositions":[],"lastnames":["Piva"],"suffixes":[]},{"firstnames":["Cid","C."],"propositions":["de"],"lastnames":["Souza"],"suffixes":[]}],"title":"The maximum common edge subgraph problem: A polyhedral investigation","journal":"Discrete Appl Math","year":"2012","volume":"160","number":"18","pages":"2523 - 2541","abstract":"In the Maximum Common Edge Subgraph Problem (MCES), given two graphs G and H with the same number of vertices, one has to find a common subgraph of G and H (not necessarily induced) with the maximum number of edges. This problem arises in parallel programming environments, and was first defined in?Bokhari (1981) [2]. This paper presents a new integer programming formulation for the MCES and a polyhedral study of this model. Several classes of valid inequalities are identified, most of which are shown to define facets. These findings were incorporated into a branch&cut algorithm we implemented. Experimental results with this algorithm are reported.","doi":"10.1016/j.dam.2012.01.026","keywords":"Maximum common subgraph problem, Graph isomorphism, Polyhedral combinatorics, Branch&cut algorithm","owner":"Sebastian","timestamp":"2019.08.04","bibtex":"@Article{bahiense12maximum,\n author = {Laura Bahiense and Gordana Mani\\'c and Breno Piva and Cid C. de Souza},\n title = {The maximum common edge subgraph problem: A polyhedral investigation},\n journal = {Discrete Appl Math},\n year = {2012},\n volume = {160},\n number = {18},\n pages = {2523 - 2541},\n abstract = {In the Maximum Common Edge Subgraph Problem (MCES), given two graphs G and H with the same number of vertices, one has to find a common subgraph of G and H (not necessarily induced) with the maximum number of edges. This problem arises in parallel programming environments, and was first defined in?Bokhari (1981) [2]. This paper presents a new integer programming formulation for the MCES and a polyhedral study of this model. Several classes of valid inequalities are identified, most of which are shown to define facets. These findings were incorporated into a branch&cut algorithm we implemented. Experimental results with this algorithm are reported.},\n doi = {10.1016/j.dam.2012.01.026},\n keywords = {Maximum common subgraph problem, Graph isomorphism, Polyhedral combinatorics, Branch&cut algorithm},\n owner = {Sebastian},\n timestamp = {2019.08.04},\n}\n\n","author_short":["Bahiense, L.","Manić, G.","Piva, B.","de Souza, C. C."],"key":"bahiense12maximum","id":"bahiense12maximum","bibbaseid":"bahiense-mani-piva-desouza-themaximumcommonedgesubgraphproblemapolyhedralinvestigation-2012","role":"author","urls":{},"keyword":["Maximum common subgraph problem","Graph isomorphism","Polyhedral combinatorics","Branch&cut algorithm"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","creationDate":"2019-11-19T17:33:11.629Z","downloads":0,"keywords":["maximum common subgraph problem","graph isomorphism","polyhedral combinatorics","branch&cut algorithm"],"search_terms":["maximum","common","edge","subgraph","problem","polyhedral","investigation","bahiense","manić","piva","de souza"],"title":"The maximum common edge subgraph problem: A polyhedral investigation","year":2012,"dataSources":["C5FtkvWWggFfMJTFX"]}