The Rectilinear Steiner Tree Problem in NP Complete Export

@article{citeulike:227163, abstract = {. The rectilinear Steiner tree problem asks for a shortest tree connecting given points in the plane with rectilinear distance. The best theoretically analyzed algorithm for this problem with a fairly practical behaviour bases on dynamic programming and has a running time of O(n 2 Δ 2:62 n ) (Ganley/Cohoon). The best implementation can solve random problems of size 35 (Salowe/Warme) within a day. In this paper we improve the theoretical worst-case time bound to O(n Δ 2:38 n ),...}, author = {Garey, M. R. and Johnson, David S.}, citeulike-article-id = {227163}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.5551}, journal = {SIAM Journal of Applied Mathematics}, keywords = {npcomplete}, pages = {826--834}, posted-at = {2008-04-14 17:54:10}, priority = {2}, title = {The Rectilinear Steiner Tree Problem in NP Complete}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.5551}, volume = {32}, year = {1977} }

TY - JOUR ID - citeulike:227163 L3 - citeulike-article-id:227163 N2 - . The rectilinear Steiner tree problem asks for a shortest tree connecting given points in the plane with rectilinear distance. The best theoretically analyzed algorithm for this problem with a fairly practical behaviour bases on dynamic programming and has a running time of O(n 2 Δ 2:62 n ) (Ganley/Cohoon). The best implementation can solve random problems of size 35 (Salowe/Warme) within a day. In this paper we improve the theoretical worst-case time bound to O(n Δ 2:38 n ),... JF - SIAM Journal of Applied Mathematics EP - 834 TI - The Rectilinear Steiner Tree Problem in NP Complete VL - 32 SP - 826 KW - npcomplete AU - Garey, MR AU - Johnson, David PY - 1977/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.5551 ER -