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

DOI10.1145/2601070zbMath1398.68667OpenAlexW2089847997MaRDI QIDQ4962150

Erik D. Demaine, Philip N. Klein, Mohammad Taghi Hajiaghayi

Publication date: 30 October 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2601070

zbMATH Keywords

planaritynetwork designapproximation algorithmsnode weights

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Approximation algorithms (68W25)

Related Items (5)

Hitting Weighted Even Cycles in Planar Graphs ⋮ An Efficient Approximation Algorithm for the Steiner Tree Problem ⋮ On the hardness of full Steiner tree problems ⋮ Approximating node-weighted \(k\)-MST on planar graphs ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)

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