DC Field | Value | Language |
---|---|---|
dc.contributor.author | Shin, Donghoon | ko |
dc.contributor.author | Choi, Sunghee | ko |
dc.date.accessioned | 2023-11-22T09:00:09Z | - |
dc.date.available | 2023-11-22T09:00:09Z | - |
dc.date.created | 2023-11-22 | - |
dc.date.created | 2023-11-22 | - |
dc.date.created | 2023-11-22 | - |
dc.date.created | 2023-11-22 | - |
dc.date.issued | 2023-11 | - |
dc.identifier.citation | PLOS ONE, v.18, no.11 | - |
dc.identifier.issn | 1932-6203 | - |
dc.identifier.uri | http://hdl.handle.net/10203/315062 | - |
dc.description.abstract | <jats:p>We present improved algorithms for the Steiner tree problem with the minimum number of Steiner points and bounded edge length. Given <jats:italic>n</jats:italic> terminal points in a 2D Euclidean plane and an edge length bound, the problem asks to construct a spanning tree of <jats:italic>n</jats:italic> terminal points with minimal Steiner points such that every edge length of the spanning tree is within the given bound. This problem is known to be NP-hard and has practical applications such as relay node placements in wireless networks, wavelength-division multiplexing(WDM) optimal network design, and VLSI design. The best-known deterministic approximation algorithm has <jats:italic>O</jats:italic>(<jats:italic>n</jats:italic><jats:sup>3</jats:sup>) running time with an approximation ratio of 3. This paper proposes an efficient approximation algorithm using the Voronoi diagram that guarantees an approximation ratio of 3 in <jats:italic>O</jats:italic>(<jats:italic>n</jats:italic> log <jats:italic>n</jats:italic>) time. We also present the first exact algorithm to find an optimal Steiner tree for given three terminal points in constant time. Using this exact algorithm, we improve the 3-approximation algorithm with better performance regarding the number of required Steiner points in <jats:italic>O</jats:italic>(<jats:italic>n</jats:italic> log <jats:italic>n</jats:italic>) time.</jats:p> | - |
dc.language | English | - |
dc.publisher | PUBLIC LIBRARY SCIENCE | - |
dc.title | An efficient 3-approximation algorithm for the Steiner tree problem with the minimum number of Steiner points and bounded edge length | - |
dc.type | Article | - |
dc.identifier.wosid | 001124507900035 | - |
dc.identifier.scopusid | 2-s2.0-85177749799 | - |
dc.type.rims | ART | - |
dc.citation.volume | 18 | - |
dc.citation.issue | 11 | - |
dc.citation.publicationname | PLOS ONE | - |
dc.identifier.doi | 10.1371/journal.pone.0294353 | - |
dc.contributor.localauthor | Choi, Sunghee | - |
dc.contributor.nonIdAuthor | Shin, Donghoon | - |
dc.description.isOpenAccess | N | - |
dc.type.journalArticle | Article | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.