An O(n log n) Approximation Scheme for Steiner Tree in Planar Graphs

被引：54

作者：

Borradaile, Glencora ^{[1
]}

Klein, Philip ^{[1
]}

Mathieu, Claire ^{[1
]}

机构：

[1] Brown Univ, Dept Comp Sci, Providence, RI 02912 USA

来源：

ACM TRANSACTIONS ON ALGORITHMS | 2009年 / 5卷 / 03期

关键词：

Steiner tree; planar graphs; approximation scheme; ALGORITHMS;

D O I：

10.1145/1541885.1541892

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We give a Polynomial-Time Approximation Scheme (PTAS) for the Steiner tree problem in planar graphs. The running time is O(n log n).

引用

页数：31

共 39 条

[1] Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems [J].

Arora, S .

JOURNAL OF THE ACM, 1998, 45 (05) :753-782

[2]

Arora S, 1998, SODA, P33

[3] APPROXIMATION ALGORITHMS FOR NP-COMPLETE PROBLEMS ON PLANAR GRAPHS [J].

BAKER, BS .

JOURNAL OF THE ACM, 1994, 41 (01) :153-180

[4] IMPROVED APPROXIMATIONS FOR THE STEINER TREE PROBLEM [J].

BERMAN, P ;

RAMAIYER, V .

JOURNAL OF ALGORITHMS, 1994, 17 (03) :381-408

[5] THE STEINER PROBLEM WITH EDGE LENGTH-1 AND LENGTH-2 [J].

BERN, M ;

PLASSMANN, P .

INFORMATION PROCESSING LETTERS, 1989, 32 (04) :171-176

[6] FASTER EXACT ALGORITHMS FOR STEINER TREES IN PLANAR NETWORKS [J].

BERN, M .

NETWORKS, 1990, 20 (01) :109-120

[7]

BERN M, 1991, MATH OPER RES, V33, P405

[8]

BORRADAILE G, 2008, P 35 INT C AUT LANG

[9]

Borradaile G, 2007, LECT NOTES COMPUT SC, V4619, P275

[10]

Borradaile G, 2007, PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P1285

← 1 2 3 4 →