Optimization Online


Facets for the Maximum Common Induced Subgraph Problem Polytope

Breno Piva(bpiva***at***ic.unicamp.br)
Cid de Souza(cid***at***ic.unicamp.br)

Abstract: This paper presents some strong valid inequalities for the Maximum Common Induced Subgraph Problem (MCIS) and the proofs that the inequalities are facet-defining under certain conditions. The MCIS is an NP-hard problem and, therefore, no polynomial time algorithm is known to solve it. In this context, the study of its polytope can help in the development of more efficient branch-and-bound and branch-and-cut algorithms.

Keywords: Combinatorial Optimization, Integer Programming, Polyhedron, Maximum Common Induced Subgraph

Category 1: Combinatorial Optimization (Polyhedra )


Download: [PDF]

Entry Submitted: 09/02/2011
Entry Accepted: 09/02/2011
Entry Last Modified: 09/02/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society