Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs

DOI10.1007/978-3-642-02927-1_28MaRDI QIDQ3638045zbMATH OpenOpenAlexFDO

Authors Erik D. Demaine, Mohammad T. Hajiaghayi, Philip N. Klein

Publication date 14 July 2009

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/1721.1/62256

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Node-weighted Steiner tree and group Steiner tree in planar graphs
• scientific article; zbMATH DE number 1303564
• scientific article; zbMATH DE number 1445376
• Approximation algorithms for node-weighted prize-collecting Steiner tree problems on planar graphs
• An improved approximation scheme for the Group Steiner Problem

Cited in

(16)

• PTAS for Steiner tree on map graphs
• Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs
• Approximation algorithms for priority Steiner tree problems
• Optimal relay node placement in delay constrained wireless sensor network design
• Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs
• A PTAS for Node-Weighted Steiner Tree in Unit Disk Graphs
• Beyond metric embedding: approximating group Steiner trees on bounded treewidth graphs
• Node-weighted Steiner tree and group Steiner tree in planar graphs
• Parameterized complexity of directed Steiner tree on sparse graphs
• A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting
• A PTAS for the Steiner forest problem in doubling metrics
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings
• Approximating node-weighted \(k\)-MST on planar graphs
• Approximating node-weighted \(k\)-MST on planar graphs
• Approximation algorithms for the maximum connected submodular functions
• Connected k-median with disjoint and non-disjoint clusters

This page was built for publication: Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3638045)