### Abstract

The metric dimension of a graph G is the smallest size of a set R of vertices that can distinguish each vertex pair of G by the shortest-path distance to some vertex in R. Computing the metric dimension is NP-hard, even when restricting inputs to bipartite graphs. We present a linear-time algorithm for computing the metric dimension for chain graphs, which are bipartite graphs whose vertices can be ordered by neighborhood inclusion.

Original language | English |
---|---|

Pages (from-to) | 671-676 |

Journal | Information processing letters |

Volume | 115 |

Issue number | 9 |

DOIs | |

Publication status | Published - 2015 |

Externally published | Yes |

## Fingerprint Dive into the research topics of 'Computing the metric dimension for chain graphs'. Together they form a unique fingerprint.

## Cite this

Fernau, H., Heggernes, P., van 't Hof, P., Meister, D., & Saei, R. (2015). Computing the metric dimension for chain graphs.

*Information processing letters*,*115*(9), 671-676. https://doi.org/10.1016/j.ipl.2015.04.006