On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs

DOI10.1007/S00453-020-00674-XMaRDI QIDQ786037zbMATH OpenOpenAlexFDO

Authors Florian Barbero, Lucas Isenmann, Jocelyn Thiebaut

Publication date 12 August 2020

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-020-00674-x

zbMATH Keywords

distance-identifying sethitting setidentifying codemeta-problemmetric dimensionparameterized complexityresolving setW-hierarchy

Mathematics Subject Classification ID

Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
• The complexity of the identifying code problem in restricted graph classes
• Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs

Cites work

• A linear time algorithm for metric dimension of cactus block graphs
• Computing the metric dimension for chain graphs
• Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
• Domination and location in acyclic graphs
• How complex are random graphs in first order logic?
• scientific article; zbMATH DE number 4053685 (Why is no real title available?)
• scientific article; zbMATH DE number 4070954 (Why is no real title available?)
• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Induced subsets
• Metric Dimension of Bounded Tree-length Graphs
• Minimal identifying codes in trees and planar graphs with large girth
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• Network verification via routing table queries
• On a new class of codes for identifying vertices in graphs
• On identifying codes
• On separating systems
• On the Complexity of Canonical Labeling of Strongly Regular Graphs
• On the Complexity of Metric Dimension
• The (weighted) metric dimension of graphs: hard and easy cases
• Which problems have strongly exponential complexity?

Cited in

(7)

• Metric dimension parameterized by treewidth
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs
• Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
• Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover
• Structural parameterization of locating-dominating set and test cover
• Tight (double) exponential bounds for identification problems: locating-dominating set and test cover

This page was built for publication: On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q786037)