Name
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. We show how to compute the metric dimension of bipartite chain graphs.Our algorithm works in linear time even on compact representations.We also conclude combinatorial results for simple chain graphs.Our order-theoretic arguments may be useful for other problems, as well.We indicate this for some variants of metric dimension. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.ipl.2015.04.006 | Information Processing Letters |
Keywords | Field | DocType |
Combinatorial problems,Metric dimension,Adjacency metric dimension,Chain graphs,Polynomial-time algorithms | Hausdorff dimension,Discrete mathematics,Combinatorics,Metric k-center,Intrinsic metric,Metric (mathematics),Dimension function,Equilateral dimension,Packing dimension,Mathematics,Metric dimension | Journal |
Volume | Issue | ISSN |
115 | 9 | 0020-0190 |
Citations | PageRank | References |
6 | 0.49 | 15 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Henning Fernau | 1 | 1646 | 162.68 |
| Pinar Heggernes | 2 | 845 | 72.39 |
| Pim van 't Hof | 3 | 209 | 20.75 |
| Daniel Meister | 4 | 144 | 17.61 |
| Reza Saei | 5 | 24 | 3.62 |