Approximation schemes for node-weighted geometric Steiner tree problems

DOI10.1007/S00453-007-9114-6MaRDI QIDQ2391178zbMATH OpenOpenAlexFDO

Authors Jan Remy, Angelika Steger

Publication date 24 July 2009

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/20.500.11850/157324

zbMATH Keywords

approximation schemescomputational geometrySteiner tree problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• An approximation scheme for some Steiner tree problems in the plane
• scientific article; zbMATH DE number 1555959
• New approximation algorithms for the Steiner tree problems
• Approximation schemes for NP-hard geometric optimization problems: a survey

Cites work

• A General Approximation Technique for Constrained Forest Problems
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• A proof of the Gilbert-Pollak conjecture on the Steiner ratio
• A quasi-polynomial time approximation scheme for minimum weight triangulation
• Approximation algorithms for constrained node weighted Steiner tree problems
• Approximation schemes for degree-restricted MST and red-blue separation problems
• Approximation schemes for NP-hard geometric optimization problems: a survey
• Bypassing the embedding
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• How Long Can a Euclidean Traveling Salesman Tour Be?
• scientific article; zbMATH DE number 3588048 (Why is no real title available?)
• scientific article; zbMATH DE number 2001186 (Why is no real title available?)
• scientific article; zbMATH DE number 1559518 (Why is no real title available?)
• scientific article; zbMATH DE number 1775394 (Why is no real title available?)
• scientific article; zbMATH DE number 871938 (Why is no real title available?)
• scientific article; zbMATH DE number 1445376 (Why is no real title available?)
• scientific article; zbMATH DE number 970831 (Why is no real title available?)
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• The Complexity of Computing Steiner Minimal Trees
• The node-weighted steiner tree problem
• The Steiner problem with edge lengths 1 and 2
• The Steiner tree problem
• The Travelling Salesman Problem and Minimum Matching in the Unit Square

Cited in

(12)

• Approximation schemes for NP-hard geometric optimization problems: a survey
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• Approximation algorithms for constructing required subgraphs using stock pieces of fixed length
• A PTAS for the geometric connected facility location problem
• Optimal relay node placement in delay constrained wireless sensor network design
• The node-weighted steiner tree problem
• scientific article; zbMATH DE number 913344 (Why is no real title available?)
• scientific article; zbMATH DE number 7378704 (Why is no real title available?)
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs
• Solving the prize‐collecting Euclidean Steiner tree problem
• Approximation algorithms for constructing Steiner trees in the Euclidean plane \(\mathbb{R}^2\) using stock pieces of materials with fixed length

This page was built for publication: Approximation schemes for node-weighted geometric Steiner tree problems

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