On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs
type: Item
instance of: scholarly article
title: On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs
zbMATH Open document ID: 1452.68131
author: Florian Barbero
author: Lucas Isenmann
author: Jocelyn Thiebaut
published in: Algorithmica
publication date: 2020-08-12T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q27
zbMATH DE Number: 7233375
zbMATH Keywords: identifying code
zbMATH Keywords: resolving set
zbMATH Keywords: metric dimension
zbMATH Keywords: distance-identifying set
zbMATH Keywords: parameterized complexity
zbMATH Keywords: W-hierarchy
zbMATH Keywords: meta-problem
zbMATH Keywords: hitting set
MaRDI profile type: Publication
full work available at URL: s00453-020-00674-x
OpenAlex ID: W2962995830
cites work: Minimal identifying codes in trees and planar graphs with large girth
cites work: On the Complexity of Canonical Labeling of Strongly Regular Graphs
cites work: Network verification via routing table queries
cites work: Metric Dimension of Bounded Tree-length Graphs
cites work: On separating systems
cites work: Induced subsets
cites work: Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
cites work: Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
cites work: On identifying codes
cites work: Q3789614
cites work: On the Complexity of Metric Dimension
cites work: The (weighted) metric dimension of graphs: hard and easy cases
cites work: Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
cites work: Computing the metric dimension for chain graphs
cites work: Q4198056
cites work: Q4119237
cites work: A linear time algorithm for metric dimension of cactus block graphs
cites work: Which problems have strongly exponential complexity?
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: Q4075485
cites work: Domination and location in acyclic graphs
cites work: Q3803159
DOI: 10.1007/S00453-020-00674-X
description: scientific article; zbMATH DE number 7233375