scientific article; zbMATH DE number 1003287

MaRDI QIDQ3128917zbMATH OpenFDO

Authors R. Ravi, Ravi Sundaram, S. S. Ravi, Madhav V. Marathe, Daniel J. Rosenkrantz

Publication date 4 August 1997

zbMATH Keywords

network designedge-weighted graph\(k\)MST problempolynomial-time exact solutions

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A constant-factor approximation algorithm for the \(k\)-MST problem
• Low-Degree Spanning Trees of Small Weight
• scientific article; zbMATH DE number 1256763

Cited in

(28)

• Finding Subsets Maximizing Minimum Structures
• scientific article; zbMATH DE number 910870 (Why is no real title available?)
• Shape rectangularization problems in intensity-modulated radiation therapy
• On the approximability of some maximum spanning tree problems
• An O\((\log k)\)-approximation algorithm for the \(k\) minimum spanning tree problem in the plane
• Low-light trees, and tight lower bounds for Euclidean spanners
• Faster geometric \(k\)-point MST approximation
• An O( k) approximation algorithm for the k minimum spanning tree problem in the plane
• Heuristics with Constant Error Guarantees for the Design of Tree Networks
• A constant-factor approximation algorithm for the \(k\)-MST problem
• Approximating the weight of shallow Steiner trees
• A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design
• \(k\)-edge subgraph problems
• On the approximability of some Maximum Spanning Tree Problems
• scientific article; zbMATH DE number 1947056 (Why is no real title available?)
• Balls and funnels: energy efficient group-to-group anycasts
• The minimum spanning tree problem with non-terminal set
• A note on the $k$-minimum spanning tree problem on circles
• Solving energy issues for sweep coverage in wireless sensor networks
• Maintaining spanning trees of small diameter
• Short trees in polygons
• Improved Steiner tree algorithms for bounded treewidth
• Approximating node-weighted \(k\)-MST on planar graphs
• Saving an epsilon: a 2-approximation for the k-MST problem in graphs
• scientific article; zbMATH DE number 176576 (Why is no real title available?)
• scientific article; zbMATH DE number 437549 (Why is no real title available?)
• Service-constrained network design problems
• Complexity and approximability of certain bicriteria location problems

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 Q3128917)