Skip to main content

Research Repository

Advanced Search

Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs

Foucaud, F.; Mertzios, G.B.; Naserasr, R.; Parreau, A.; Valicov, P.

Authors

F. Foucaud

R. Naserasr

A. Parreau

P. Valicov



Contributors

Ernst W. Mayr
Editor

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.

Citation

Foucaud, F., Mertzios, G., Naserasr, R., Parreau, A., & Valicov, P. (2016). Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs. In E. W. Mayr (Ed.), Graph-theoretic concepts in computer science : 41st international workshop, WG 2015, Garching, Germany, June 17-19, 2015 ; revised papers (456-471). https://doi.org/10.1007/978-3-662-53174-7_32

Conference Name 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG)
Conference Location Munich, Germany
Acceptance Date Apr 28, 2015
Online Publication Date Aug 5, 2016
Publication Date Aug 5, 2016
Deposit Date May 21, 2015
Publicly Available Date Mar 28, 2024
Pages 456-471
Series Title Lecture notes in computer science
Series Number 9224
Series ISSN 0302-9743,1611-3349
Book Title Graph-theoretic concepts in computer science : 41st international workshop, WG 2015, Garching, Germany, June 17-19, 2015 ; revised papers.
ISBN 9783662531730
DOI https://doi.org/10.1007/978-3-662-53174-7_32
Public URL https://durham-repository.worktribe.com/output/1152441

Files





You might also like



Downloadable Citations