F. Foucaud
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
Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
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
Accepted Conference Proceeding
(0)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-53174-7_32
You might also like
Graphs with minimum fractional domatic number
(2023)
Journal Article
Approximate and Randomized algorithms for Computing a Second Hamiltonian Cycle
(2023)
Journal Article
Sliding into the Future: Investigating Sliding Windows in Temporal Graphs
(2023)
Conference Proceeding
Fast parameterized preprocessing for polynomial-time solvable graph problems
(2023)
Journal Article
The complexity of computing optimum labelings for temporal connectivity
(2022)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search