Polynomial time approximation scheme for the rectilinear Steiner arborescence problem

DOI10.1023/A:1009826311973MaRDI QIDQ1587590zbMATH OpenOpenAlexFDO

Authors B. Lu, Lu Ruan

Publication date 7 October 2001

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1009826311973

zbMATH Keywords

approximation algorithmarborescencePTASVLSI designSteiner terminals

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Recommendations

• Polynomial time approximation scheme for symmetric rectilinear Steiner arborescence problem
• The rectilinear Steiner arborescence problem
• scientific article; zbMATH DE number 6381762
• Subexponential algorithms for rectilinear Steiner tree and arborescence problems
• Subexponential algorithms for rectilinear Steiner tree and arborescence problems
• Faster approximation algorithms for the rectilinear Steiner tree problem
• scientific article; zbMATH DE number 7053305
• A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
• scientific article; zbMATH DE number 1445377
• The Rectilinear Steiner Arborescence Problem Is NP-Complete

Cited in

(11)

• Linear-size planar Manhattan network for convex point sets
• Polynomial time approximation scheme for symmetric rectilinear Steiner arborescence problem
• Approximating the generalized minimum Manhattan network problem
• Angle-restricted Steiner arborescences for flow map layout
• scientific article; zbMATH DE number 1985307 (Why is no real title available?)
• scientific article; zbMATH DE number 1445377 (Why is no real title available?)
• Dynamic programming approach to the generalized minimum Manhattan network problem
• A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
• The Rectilinear Steiner Arborescence Problem Is NP-Complete
• Optimal competitiveness for the rectilinear Steiner arborescence problem
• Non-crossing geometric Steiner arborescences

This page was built for publication: Polynomial time approximation scheme for the rectilinear Steiner arborescence problem

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