The Complexity of the Identifying Code Problem in Restricted Graph Classes
From MaRDI portal
Publication:2870024
DOI10.1007/978-3-642-45278-9_14zbMath1407.68219OpenAlexW78868202MaRDI QIDQ2870024
Publication date: 17 January 2014
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-45278-9_14
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (7)
The identifying code, the locating-dominating, the open locating-dominating and the locating total-dominating problems under some graph operations ⋮ A linear-time algorithm for the identifying code problem on block graphs ⋮ Some results about a conjecture on identifying codes in complete suns ⋮ Progress on the description of identifying code polyhedra for some families of split graphs ⋮ Polyhedra associated with identifying codes in graphs ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ Polyhedra associated with locating-dominating, open locating-dominating and locating total-dominating sets in graphs
This page was built for publication: The Complexity of the Identifying Code Problem in Restricted Graph Classes