Polyhedra associated with identifying codes in graphs

DOI10.1016/j.dam.2017.06.005zbMath1433.90198OpenAlexW2735965034MaRDI QIDQ1752479

Yanina P. Lucarini, Annegret K. Wagler, Silvia M. Bianchi, Gabriela R. Argiroffo

Publication date: 24 May 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2017.06.005

zbMATH Keywords

identifying code clutteridentifying code polyhedronodd hypercycles

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

The identifying code, the locating-dominating, the open locating-dominating and the locating total-dominating problems under some graph operations ⋮ Linear-time algorithms for three domination-based separation problems in block graphs ⋮ Locating-Domination and Identification ⋮ Polyhedra associated with locating-dominating, open locating-dominating and locating total-dominating sets in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• On graphs having a \(V\setminus \{x\}\) set as an identifying code
• Minimal identifying codes in trees and planar graphs with large girth
• On the set covering polyhedron of circulant matrices
• On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
• On the facial structure of the set covering polytope
• Facets and lifting procedures for the set covering polytope
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• Identifying and locating-dominating codes on chains and cycles
• Combinatorial Optimization
• The Complexity of the Identifying Code Problem in Restricted Graph Classes
• Study of Identifying Code Polyhedra for Some Families of Split Graphs
• On a new class of codes for identifying vertices in graphs
• Identifying Codes in Line Graphs