Polyhedra associated with identifying codes in graphs

DOI10.1016/J.DAM.2017.06.005MaRDI QIDQ1752479zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Study of identifying code polyhedra for some families of split graphs
• Progress on the description of identifying code polyhedra for some families of split graphs
• The complexity of the identifying code problem in restricted graph classes
• Identifying codes in some subgraphs of the square lattice
• Identifying codes in trees and planar graphs

Cites work

• scientific article; zbMATH DE number 1735664 (Why is no real title available?)
• scientific article; zbMATH DE number 3345048 (Why is no real title available?)
• Combinatorial optimization. Packing and covering
• Facets and lifting procedures for the set covering polytope
• Identifying and locating-dominating codes on chains and cycles
• Identifying codes in line graphs
• Minimal identifying codes in trees and planar graphs with large girth
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• On a new class of codes for identifying vertices in graphs
• On graphs having a \(V\setminus \{x\}\) set as an identifying code
• On the facial structure of the set covering polytope
• On the set covering polyhedron of circulant matrices
• On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
• Study of identifying code polyhedra for some families of split graphs
• The complexity of the identifying code problem in restricted graph classes

Cited in

(10)

• Codes associated with generalized polygons
• Progress on the description of identifying code polyhedra for some families of split graphs
• Study of identifying code polyhedra for some families of split graphs
• Locating-domination and identification
• On three domination-based identification problems in block graphs
• A linear-time algorithm for the identifying code problem on block graphs
• scientific article; zbMATH DE number 729870 (Why is no real title available?)
• Linear-time algorithms for three domination-based separation problems in block graphs
• The identifying code, the locating-dominating, the open locating-dominating and the locating total-dominating problems under some graph operations
• Polyhedra associated with locating-dominating, open locating-dominating and locating total-dominating sets in graphs

This page was built for publication: Polyhedra associated with identifying codes in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1752479)