Distance domination and amplifier placement problems

MaRDI QIDQ5487907zbMATH OpenFDO

Authors

Publication date 13 September 2006

zbMATH Keywords

amplified spanning treeNP-complete

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph theory (including graph drawing) in computer science (68R10) 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)