On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs

DOI10.4230/LIPIcs.IPEC.2018.10OpenAlexW3004026509MaRDI QIDQ5009472

Florian Barbero, Lucas Isenmann, Jocelyn Thiebaut

Publication date: 4 August 2021

Full work available at URL: https://arxiv.org/abs/1810.03868

zbMATH Keywords

parameterized complexityresolving setmetric dimensionidentifying codehitting setW-hierarchymeta-problemdistance identifying set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx)

Related Items (1)

On finding the best and worst orientations for the metric dimension

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The (weighted) metric dimension of graphs: hard and easy cases
• Network verification via routing table queries
• The metric dimension of Cayley digraphs
• On separating systems
• Minimal identifying codes in trees and planar graphs with large girth
• Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Induced subsets
• On the Complexity of Metric Dimension
• Domination and location in acyclic graphs
• On the Complexity of Canonical Labeling of Strongly Regular Graphs
• On a new class of codes for identifying vertices in graphs
• How complex are random graphs in first order logic?

This page was built for publication: On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs