Distance domination and amplifier placement problems

MaRDI QIDQ5487907zbMATH OpenFDO

Authors

Publication date 13 September 2006

zbMATH Keywords

NP-completeamplified spanning tree

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Transportation, logistics and supply chain management (90B06)

Recommendations

• NP-completeness of minimum spanner problems
• Degree-preserving spanning trees in small-degree graphs
• Tree Spanners
• The minimum stretch spanning tree problem for typical graphs
• Complexity results for the spanning tree congestion problem

This page was built for publication: Distance domination and amplifier placement problems

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