Foucaud, F. and Mertzios, G.B. and Naserasr, R. and Parreau, A. and Valicov, P. (2016) 'Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs.', in Graph-theoretic concepts in computer science : 41st international workshop, WG 2015, Garching, Germany, June 17-19, 2015 ; revised papers. Berlin: Springer, pp. 456-471. Lecture notes in computer science. (9224).
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.
|Item Type:||Book chapter|
|Full text:||(AM) Accepted Manuscript|
Download PDF (401Kb)
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-662-53174-7_32|
|Publisher statement:||The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-53174-7_32|
|Date accepted:||28 April 2015|
|Date deposited:||03 August 2015|
|Date of first online publication:||05 August 2016|
|Date first made open access:||05 August 2017|
Save or Share this output
|Look up in GoogleScholar|