Complexity of metric dimension on planar graphs
详细信息 查看全文
- 作者：Josep Diaza ; b ; 1 ; diaz@cs.upc.edu" class="auth_mail" title="E-mail the corresponding author ; Olli Pottonena ; 2 ; 3 ; olli.pottonen@iki.fi" class="auth_mail" title="E-mail the corresponding author ; Maria Sernaa ; b ; 1 ; mjserna@cs.upc.edu" class="auth_mail" title="E-mail the corresponding author ; Erik Jan van Leeuwenc ; 4 ; erikjan@mpi-inf.mpg.de" class="auth_mail" title="E-mail the corresponding author
- 关键词：Metric dimension ; Planar graph ; Outerplanar graph ; NP-completeness
- 刊名：Journal of Computer and System Sciences
- 出版年：2017
- 出版时间：February 2017
- 年：2017
- 卷：83
- 期：1
- 页码：132-158
- 全文大小：887 K
文摘
- •
In Metric Dimension, we distinguish all pairs of vertices by few selected landmarks.
- •
We show that Metric Dimension is NP-complete on planar graphs.
- •
We show that Metric Dimension has a polynomial-time algorithm on outerplanar graphs.
- •
This closes a 30-year old complexity gap for Metric Dimension.