Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
type: Item
instance of: scholarly article
title: Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
zbMATH Open document ID: 1325.05166
author: Florent Foucaud
published in: Journal of Discrete Algorithms
publication date: 2015-03-24T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6419169
zbMATH Keywords: test cover
zbMATH Keywords: separating system
zbMATH Keywords: identifying code
zbMATH Keywords: locating-dominating set
zbMATH Keywords: NP-completeness
zbMATH Keywords: approximation
MaRDI profile type: Publication
full work available at URL: j.jda.2014.08.004
OpenAlex ID: W1973765739
cites work: Some APX-completeness results for cubic graphs
cites work: Minimal identifying codes in trees and planar graphs with large girth
cites work: Complexity results for identifying codes in planar graphs
cites work: Q4258216
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: Dominating sets for split and bipartite graphs
cites work: On separating systems
cites work: Dominating Sets in Chordal Graphs
cites work: Graph Classes: A Survey
cites work: Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
cites work: Discriminating codes in (bipartite) planar graphs
cites work: Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
cites work: Approximation hardness of edge dominating set problems
cites work: Approximation hardness of dominating set problems in bounded degree graphs
cites work: Unit disk graphs
cites work: Q3789614
cites work: Dominating sets in perfect graphs
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Monadic second-order evaluations on tree-decomposable graphs
cites work: Structure in Approximation Classes
cites work: Domination in convex and chordal bipartite graphs
cites work: Approximation algorithms for the test cover problem
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: Domination in permutation graphs
cites work: The Complexity of the Identifying Code Problem in Restricted Graph Classes
cites work: Identifying Codes in Line Graphs
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: Q4198056
cites work: Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
cites work: Q4368728
cites work: Q4368729
cites work: NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
cites work: Approximation algorithms for combinatorial problems
cites work: On a new class of codes for identifying vertices in graphs
cites work: How complex are random graphs in first order logic?
cites work: Domination and total domination on asteroidal triple-free graphs
cites work: Identifying Codes and Covering Problems
cites work: The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
cites work: Identifying and Locating–Dominating Codes in (Random) Geometric Networks
cites work: Approximation and Online Algorithms
cites work: Optimization, approximation, and complexity classes
cites work: Q4527015
cites work: Q3279628
cites work: Domination and location in acyclic graphs
cites work: Q3684148
cites work: Approximability of identifying codes and locating-dominating codes
cites work: Edge Dominating Sets in Graphs
DOI: 10.1016/J.JDA.2014.08.004
description: scientific article; zbMATH DE number 6419169