Polynomial time approximation scheme for the rectilinear Steiner arborescence problem

DOI10.1023/A:1009826311973zbMath0969.90074OpenAlexW1503993426MaRDI QIDQ1587590

Bing 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 algorithmVLSI designPTASarborescenceSteiner terminals

Mathematics Subject Classification ID

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

Related Items

Linear-size planar Manhattan network for convex point sets ⋮ Optimal Competitiveness for the Rectilinear Steiner Arborescence Problem ⋮ Flip distance between triangulations of a simple polygon is NP-complete ⋮ Approximating the generalized minimum Manhattan network problem ⋮ Approximating minimum Manhattan networks in higher dimensions ⋮ Dynamic programming approach to the generalized minimum Manhattan network problem ⋮ Non-crossing geometric steiner arborescences ⋮ Angle-restricted Steiner arborescences for flow map layout

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