Polyhedra associated with identifying codes in graphs

Abstract : 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 special graphs, and discuss further lines of research in order to obtain strong lower bounds stemming from linear relaxations of the identifying code polyhedron, enhanced by suitable cutting planes to be used in a B&C framework.
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

Contributor : Annegret Wagler <>
Submitted on : Wednesday, February 13, 2019 - 10:59:18 AM
Last modification on : Monday, January 20, 2020 - 12:14:06 PM
Long-term archiving on: Tuesday, May 14, 2019 - 3:40:07 PM


Files produced by the author(s)


  • HAL Id : hal-02017458, version 1



Gabriela Argiroffo, Silvia Bianchi, Yanina P.Lucarini, Annegret K. Wagler. Polyhedra associated with identifying codes in graphs. Discrete Applied Mathematics, Elsevier, 2018, 245, pp.16-27. ⟨hal-02017458⟩



Record views


Files downloads