scientific article

zbMath1277.68088MaRDI QIDQ2867320

Ralf Klasing, Sylvain Gravier, Julien Moncel

Publication date: 11 December 2013

Full work available at URL: http://journals.hil.unb.ca/index.php/AOR/article/view/2808

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

combinatorial optimizationfault tolerancegraph algorithmsapproximation algorithmsidentifying codesdomination problemsapproximation hardnesslocating-dominating codes

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Other types of codes (94B60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Applications of graph theory to circuits and networks (94C15) Approximation algorithms (68W25)

Related Items

Identifying Codes in Line Graphs ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity ⋮ Identifying codes in vertex-transitive graphs and strongly regular graphs ⋮ Bounds and extremal graphs for total dominating identifying codes ⋮ The \textsc{Red-Blue Separation} problem on graphs ⋮ Unique (optimal) solutions: complexity results for identifying and locating-dominating codes ⋮ Complexity results for identifying codes in planar graphs ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds. ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ Locating-dominating codes in paths ⋮ The compared costs of domination location-domination and identification ⋮ Network verification via routing table queries ⋮ Locating-Domination and Identification ⋮ Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs ⋮ Locating-dominating sets: from graphs to oriented graphs