**Reference**:- Erik D. Demaine, MohammadTaghi Hajiaghayi, and Philip Klein, “Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs”, in
*Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009)*, Lecture Notes in Computer Science, volume 5555, Rhodes, Greece, July 5–12, 2009, pages 328–340. **Abstract**:-
We improve the approximation ratios for two optimization problems in planar
graphs. For node-weighted Steiner tree, a classical network-optimization
problem, the best achievable approximation ratio in general graphs is
Θ(log
*n*), and nothing better was previously known for planar graphs. We give a constant-factor approximation for planar graphs. Our algorithm generalizes to allow as input any nontrivial minor-closed graph family, and also generalizes to address other optimization problems such as Steiner forest, prize-collecting Steiner tree, and network-formation games.The second problem we address is group Steiner tree: given a graph with edge weights and a collection of groups (subsets of nodes), find a minimum-weight connected subgraph that includes at least one node from each group. The best approximation ratio known in general graphs is

*O*(log^{3}*n*), or*O*(log^{2}*n*) when the host graph is a tree. We obtain an*O*(log*n*polyloglog*n*) approximation algorithm for the special case where the graph is planar embedded and each group is the set of nodes on a face. We obtain the same approximation ratio for the minimum-weight tour that must visit each group. **Comments**:- This paper is also available from SpringerLink.
**Copyright**:- Copyright held by the authors.
**Length**:- The paper is 12 pages.
**Availability**:- The paper is available in PostScript (426k), gzipped PostScript (187k), and PDF (237k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.