Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity.

Foucaud, F. and Mertzios, G.B. and Naserasr, R. and Parreau, A. and Valicov, P. (2016) 'Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity.', Algorithmica., 78 (3). pp. 914-944.

Abstract

We consider the problems of finding optimal identifying codes, (open) locating-dominating sets and resolving sets (denoted Identifying Code, (Open) Open Locating-Dominating Set and Metric Dimension) of an interval or a permutation graph. In these problems, one asks to distinguish all vertices of a graph by a subset of the vertices, using either the neighbourhood within the solution set or the distances to the solution vertices. Using a general reduction for this class of problems, we prove that the decision problems associated to these four notions are NP-complete, even for interval graphs of diameter 2 and permutation graphs of diameter 2. While Identifying Code and (Open) Locating-Dominating Set are trivially fixed-parameter-tractable when parameterized by solution size, it is known that in the same setting Metric Dimension is W[2]-hard. We show that for interval graphs, this parameterization of Metric Dimension is fixed-parameter-tractable.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
(634Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1007/s00453-016-0184-1
Publisher statement:The final publication is available at Springer via https://doi.org/10.1007/s00453-016-0184-1
Date accepted:06 July 2016
Date deposited:02 September 2016
Date of first online publication:14 July 2016
Date first made open access:14 July 2017

Save or Share this output

Export:
Export
Look up in GoogleScholar