NP-completeness of minimum spanner problems

DOI10.1016/0166-218X(94)90073-6zbMath0788.68057MaRDI QIDQ1315465

Leizhen Cai

Publication date: 10 March 1994

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

digraphsoriented graphsNP-completespanning subgraph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (22)

Graph spanners in the streaming model: An experimental study ⋮ Small stretch \((\alpha ,\beta )\)-spanners in the streaming model ⋮ Light graphs with small routing cost ⋮ Minimum \(t\)-spanners on subcubic graphs ⋮ Parameterized complexity of directed spanner problems ⋮ Restrictions of minimum spanner problems ⋮ A PTAS for the sparsest 2-spanner of 4-connected planar triangulations ⋮ Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs ⋮ Spanners and message distribution in networks. ⋮ COMPUTING GEOMETRIC MINIMUM-DILATION GRAPHS IS NP-HARD ⋮ Combinatorial network abstraction by trees and distances ⋮ Parameterized Complexity of Directed Spanner Problems. ⋮ A linear time algorithm to construct a tree 4-spanner on trapezoid graphs ⋮ An optimal parallel algorithm to construct a tree 3-spanner on interval graphs ⋮ Tree spanners in planar graphs ⋮ Max-stretch reduction for tree spanners ⋮ Approximating \(k\)-spanner problems for \(k>2\) ⋮ Graph spanners: a tutorial review ⋮ NP-hardness and fixed-parameter tractability of the minimum spanner problem ⋮ ON SPANNERS OF GEOMETRIC GRAPHS ⋮ Sparsification lower bound for linear spanners in directed graphs ⋮ Edge-disjoint spanners of complete graphs and complete digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Reconstructing the shape of a tree from observed dissimilarity data
• Delaunay graphs are almost as good as complete graphs
• On sparse spanners of weighted graphs
• Easy problems for tree-decomposable graphs
• Graph spanners
• Generating Sparse 2-Spanners
• Tree Spanners
• Grid spanners

This page was built for publication: NP-completeness of minimum spanner problems