On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs
DOI10.1007/s00453-020-00674-xzbMath1452.68131OpenAlexW2962995830MaRDI QIDQ786037
Lucas Isenmann, Florian Barbero, 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
parameterized complexityresolving setmetric dimensionidentifying codehitting setW-hierarchydistance-identifying setmeta-problem
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear time algorithm for metric dimension of cactus block graphs
- The (weighted) metric dimension of graphs: hard and easy cases
- Network verification via routing table queries
- 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.
- Which problems have strongly exponential complexity?
- Computing the metric dimension for chain graphs
- 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?
- Metric Dimension of Bounded Tree-length Graphs
This page was built for publication: On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs
