scientific article; zbMATH DE number 1107724

MaRDI QIDQ4373672zbMATH OpenFDO

Authors Ulrik Brandes, Dagmar Handke

Publication date 16 February 1998

zbMATH Keywords

distanceNP-completeNP-hardspannersparsenesstotal edge weight

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1375574
• NP-completeness of minimum spanner problems
• NP-hardness and fixed-parameter tractability of the minimum spanner problem
• NP-completeness of the Planar Separator Problems
• Approximation algorithms for NP-complete problems on planar graphs
• Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs
• New hardness results for planar graph problems in p and an algorithm for sparsest cut
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• A special planar satisfiability problem and a consequence of its NP- completeness

Cited in

(11)

• NP-completeness of minimum spanner problems
• A polynomial algorithm for finding \(T\)-span of generalized cacti
• NP-hardness and fixed-parameter tractability of the minimum spanner problem
• Additive sparse spanners for graphs with bounded length of largest induced cycle
• Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs
• scientific article; zbMATH DE number 1375574 (Why is no real title available?)
• Minimum weight Euclidean t-spanner is NP-hard
• On Spanners of Geometric Graphs
• Tree spanners in planar graphs
• Complexity of the multiobjective minimum weight minimum stretch spanner problem
• A PTAS for the sparsest 2-spanner of 4-connected planar triangulations

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4373672)