NP-Completeness Results for Minimum Planar Spanners


Dateien zu dieser Ressource

Prüfsumme: MD5:038d353548ae1fc2d8d76f1b1a37a0ff

BRANDES, Ulrik, Dagmar HANDKE, 1996. NP-Completeness Results for Minimum Planar Spanners

@techreport{Brandes1996NPCom-6371, series={Konstanzer Schriften in Mathematik und Informatik}, title={NP-Completeness Results for Minimum Planar Spanners}, year={1996}, number={16}, author={Brandes, Ulrik and Handke, Dagmar} }

Brandes, Ulrik Handke, Dagmar Handke, Dagmar 1996 application/pdf For any fixed parameter t>=1, a 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 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>=3, and for planar unweighted graphs and digraphs if t>=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 planar t-spanners and establish its NP-hardness for similar fixed values of t. 2011-03-24T16:12:16Z NP-Completeness Results for Minimum Planar Spanners eng 2011-03-24T16:12:16Z terms-of-use Brandes, Ulrik

Dateiabrufe seit 01.10.2014 (Informationen über die Zugriffsstatistik)

preprint_016.pdf 98

Das Dokument erscheint in:

KOPS Suche


Mein Benutzerkonto