scientific article

zbMath0867.90120MaRDI QIDQ3128917

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

Publication date: 4 August 1997

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Related Items (17)

Service-constrained network design problems ⋮ \(k\)-edge subgraph problems ⋮ Faster geometric \(k\)-point MST approximation ⋮ On the approximability of some maximum spanning tree problems ⋮ On the approximability of some Maximum Spanning Tree Problems ⋮ Improved Steiner tree algorithms for bounded treewidth ⋮ Complexity and approximability of certain bicriteria location problems ⋮ An O\((\log k)\)-approximation algorithm for the \(k\) minimum spanning tree problem in the plane ⋮ Shape rectangularization problems in intensity-modulated radiation therapy ⋮ Low-light trees, and tight lower bounds for Euclidean spanners ⋮ A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design ⋮ Approximating node-weighted \(k\)-MST on planar graphs ⋮ Balls and Funnels: Energy Efficient Group-to-Group Anycasts ⋮ Bicriteria Network Design Problems ⋮ Approximating the weight of shallow Steiner trees ⋮ A constant-factor approximation algorithm for the \(k\)-MST problem ⋮ Solving energy issues for sweep coverage in wireless sensor networks

This page was built for publication: