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).
Abstract
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[2]-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) |
| Status: | Peer-reviewed |
| 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
| Export: | |
| Look up in GoogleScholar |
