The General Steiner Tree-Star problem.

DOI10.1016/S0020-0190(02)00271-5zbMath1042.68120OpenAlexW2045906087MaRDI QIDQ1853139

An Zhu, Samir Khuller

Publication date: 21 January 2003

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00271-5

zbMATH Keywords

Facility locationSteiner treesApproximation algorithms

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (7)

The \(p\)-arborescence star problem: formulations and exact solution approaches ⋮ Branch‐and‐cut algorithms for the ‐arborescence star problem ⋮ Branch-and-cut-and-price for capacitated connected facility location ⋮ An algorithmic framework for the exact solution of tree-star problems ⋮ MIP models for connected facility location: a theoretical and computational study ⋮ Combinatorial optimization in system configuration design ⋮ Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty

Cites Work

• The Steiner tree problem
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• Greedy Strikes Back: Improved Facility Location Algorithms
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Approximation Algorithms for Directed Steiner Problems
• Provisioning a virtual private network
• A Branch and Cut Algorithm for a Steiner Tree-Star Problem
• Unnamed Item
• Unnamed Item

This page was built for publication: The General Steiner Tree-Star problem.