Ulrik Brandes ; Dagmar Handke - NP-Completeness Results for Minimum Planar Spanners

dmtcs:257 - Discrete Mathematics & Theoretical Computer Science, January 1, 1998, Vol. 3 no. 1 - https://doi.org/10.46298/dmtcs.257
NP-Completeness Results for Minimum Planar Spanners

Authors: Ulrik Brandes 1; Dagmar Handke 1

  • 1 Faculty of Mathematics and Computer Science [Konstanz]

For any fixed parameter t greater or equal to 1, a \emph t-spanner of a graph G is a spanning subgraph in which the distance between every pair of vertices is at most t times their distance in G. A \emph minimum t-spanner is a t-spanner with minimum total edge weight or, in unweighted graphs, minimum number of edges. In this paper, we prove the NP-hardness of finding minimum t-spanners for planar weighted graphs and digraphs if t greater or equal to 3, and for planar unweighted graphs and digraphs if t greater or equal to 5. We thus extend results on that problem to the interesting case where the instances are known to be planar. We also introduce the related problem of finding minimum \emphplanar t-spanners and establish its NP-hardness for similar fixed values of t.

Volume: Vol. 3 no. 1
Published on: January 1, 1998
Imported on: March 26, 2015
Keywords: planar graphs,graph spanners,NP-completeness,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1007/bfb0053970
  • 10.1007/bfb0053970
On the hardness of approximating spanners

Consultation statistics

This page has been seen 258 times.
This article's PDF has been downloaded 212 times.