Progress on the description of identifying code polyhedra for some families of split graphs

DOI10.1016/j.disopt.2016.06.002zbMath1387.05247OpenAlexW2463730576MaRDI QIDQ1751187

Annegret K. Wagler, Silvia M. Bianchi, Gabriela R. Argiroffo

Publication date: 24 May 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2016.06.002

zbMATH Keywords

split graphspolyhedral approachidentifying code problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Polyhedra associated with locating-dominating, open locating-dominating and locating total-dominating sets in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Minimal identifying codes in trees and planar graphs with large girth
• On the set covering polyhedron of circulant matrices
• On the facial structure of 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
• A linear-time algorithm for the identifying code problem on block graphs
• Identifying codes of 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 the width—length inequality
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• Graph Classes: A Survey
• On a new class of codes for identifying vertices in graphs
• Identifying Codes in Line Graphs

This page was built for publication: Progress on the description of identifying code polyhedra for some families of split graphs