|Résumé||The identifying code problem is a newly emerging search problem, challenging both from a theoretical and a computational point of view, even for special graphs like bipartite graphs. Hence, a typical line of attack for this problem is to determine minimum identifying codes of special graphs or to provide bounds for their size.
In this work we study the associated polyhedra and present some general results on their combinatorial structure. We demonstrate how the polyhedral approach can be applied to find minimum identifying codes for particular graphs. Also we describe facet defining inequalities for the identifying code polyhedron of some bipartite graphs and odd cycles. Finally, we discuss further lines of research in order to obtain other facet defining inequalities to be added to linear relaxations of the identifying code polyhedron, in order to obtain suitable cutting planes to be used in a B&C framework. |