A polynomial time approximation scheme for the problem of interconnecting highways

DOI10.1023/A:1011497227406MaRDI QIDQ5952321zbMATH OpenOpenAlexFDO

Authors Xiuzhen Cheng, Joon-Mo Kim, B. Lu

Publication date 2001

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

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

zbMATH Keywords

dynamic programmingminimum Steiner treepatching

Mathematics Subject Classification ID

Approximation algorithms (68W25) Traffic problems in operations research (90B20) Programming involving graphs or networks (90C35) Dynamic programming (90C39)

Recommendations

• Interconnecting Highways
• CONSTRUCTING OPTIMAL HIGHWAYS
• A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
• Pricing on paths: a PTAS for the highway problem
• Pricing on paths: a PTAS for the highway problem

Cited in

(2)

• Interconnecting Highways
• TRAVELING SALESMAN PROBLEM OF SEGMENTS

This page was built for publication: A polynomial time approximation scheme for the problem of interconnecting highways

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