Constrained spanning, Steiner trees and the triangle inequality

DOI10.1007/978-0-387-98096-6_19MaRDI QIDQ3407629zbMATH OpenOpenAlexFDO

Authors Prabhu Manyem

Publication date 4 March 2010

Published in Springer Optimization and Its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-0-387-98096-6_19

zbMATH Keywords

minimum spanning treeapproximation algorithmtriangle inequalitySteiner treeAPXmaximum spanning treeasymptotic worst case ratio

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10)

Recommendations

• Constrained Steiner trees in Halin graphs
• An inequality on Steiner trees
• A constrained Steiner tree problem
• Convexity and the Steiner tree problem
• Steiner trees and convex geometries
• Diameter-constrained Steiner trees
• Algorithmic aspects of Steiner convexity and enumeration of Steiner trees
• The constrained minimum spanning tree problem
• On the restricted \(k\)-Steiner tree problem
• Constrained spanning trees and the traveling salesman problem

Cited in

(3)

• On Hop-Constrained Steiner Trees in Tree-Like Metrics
• Diameter-constrained Steiner trees
• SOFSEM 2005: Theory and Practice of Computer Science

This page was built for publication: Constrained spanning, Steiner trees and the triangle inequality

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