Publication details for Dr George MertziosFoucaud, F., Mertzios, G.B., Naserasr, R., Parreau, A. & Valicov, P. (2016), Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs, in Mayr, Ernst W. eds, Lecture notes in computer science, 9224 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG). Munich, Germany, Springer, Berlin, 456-471.
- Publication type: Conference Paper
- ISSN/ISBN: 9783662531730, 9783662531747
- DOI: 10.1007/978-3-662-53174-7_32
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
We study the problems Locating-Dominating Set and Metric Dimension, which consist of determining a minimum-size set of vertices that distinguishes the vertices of a graph using either neighbourhoods or distances. We consider these problems when restricted to interval graphs and permutation graphs. We prove that both decision problems are NP-complete, even for graphs that are at the same time interval graphs and permutation graphs and have diameter 2. While Locating-Dominating Set parameterized by solution size is trivially fixed-parameter-tractable, it is known that Metric Dimension is W-hard. We show that for interval graphs, this parameterization of Metric Dimension is fixed-parameter-tractable.