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. I. Bounds.

Foucaud, F. and Mertzios, G.B. and Naserasr, R. and Parreau, A. and Valicov, P. (2017) 'Identification, location–domination and metric dimension on interval and permutation graphs. I. Bounds.', Theoretical computer science., 668 . pp. 43-58.

Abstract

We consider the problems of finding optimal identifying codes, (open) locating–dominating sets and resolving sets of an interval or a permutation graph. In these problems, one asks to find a subset of vertices, normally called a solution set, using which all vertices of the graph are distinguished. The identification can be done by considering the neighborhood within the solution set, or by employing the distances to the solution vertices. Normally the goal is to minimize the size of the solution set then. Here we study the case of interval graphs, unit interval graphs, (bipartite) permutation graphs and cographs. For these classes of graphs we give tight lower bounds for the size of such solution sets depending on the order of the input graph. While such lower bounds for the general class of graphs are in logarithmic order, the improved bounds in these special classes are of the order of either quadratic root or linear in terms of number of vertices. Moreover, the results for cographs lead to linear-time algorithms to solve the considered problems on inputs that are cographs.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
(435Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1016/j.tcs.2017.01.006
Publisher statement:© 2017 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Date accepted:04 January 2017
Date deposited:23 January 2017
Date of first online publication:18 January 2017
Date first made open access:18 January 2018

Save or Share this output

Export:
Export
Look up in GoogleScholar