scientific article; zbMATH DE number 1003287

zbMATH Open0867.90120MaRDI QIDQ3128917FDOQ3128917

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

Publication date: 4 August 1997

Title of this publication is not available (Why is that?)

Recommendations

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

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)

Cited In (25)

• On the approximability of some maximum spanning tree problems
• Shape rectangularization problems in intensity-modulated radiation therapy
• 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
• Heuristics with Constant Error Guarantees for the Design of Tree Networks
• A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design
• A constant-factor approximation algorithm for the \(k\)-MST problem
• Approximating the weight of shallow Steiner trees
• \(k\)-edge subgraph problems
• On the approximability of some Maximum Spanning Tree Problems
• Title not available (Why is that?)
• Solving energy issues for sweep coverage in wireless sensor networks
• Balls and Funnels: Energy Efficient Group-to-Group Anycasts
• 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
• Bicriteria Network Design Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Service-constrained network design problems
• Complexity and approximability of certain bicriteria location problems
• Title not available (Why is that?)

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)