Skip to main content

Research Repository

Advanced Search

Identification, location–domination and metric dimension on interval and permutation graphs. I. Bounds

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

Identification, location–domination and metric dimension on interval and permutation graphs. I. Bounds Thumbnail


Authors

F. Foucaud

R. Naserasr

A. Parreau

P. Valicov



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.

Citation

Foucaud, F., Mertzios, G., Naserasr, R., Parreau, A., & Valicov, P. (2017). Identification, location–domination and metric dimension on interval and permutation graphs. I. Bounds. Theoretical Computer Science, 668, 43-58. https://doi.org/10.1016/j.tcs.2017.01.006

Journal Article Type Article
Acceptance Date Jan 4, 2017
Online Publication Date Jan 18, 2017
Publication Date Mar 15, 2017
Deposit Date Jan 21, 2017
Publicly Available Date Jan 18, 2018
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 668
Pages 43-58
DOI https://doi.org/10.1016/j.tcs.2017.01.006

Files





You might also like



Downloadable Citations