• DocumentCode
    2079506
  • Title

    A Parallel Local Search Algorithm for Euclidean Steiner Tree Problem

  • Author

    Muhammad, Rashid Bin

  • Author_Institution
    Dept. of Comput. Sci., Kent State Univ.
  • fYear
    2006
  • fDate
    19-20 June 2006
  • Firstpage
    157
  • Lastpage
    164
  • Abstract
    This paper presented a parallel local search algorithm for the Steiner tree problem. The main contribution of this work is the O(n2 log2 n + log n log(n/ log n)) parallel local search algorithm for computing Steiner tree on the Euclidean plane. The algorithm used proximity structures from computational geometry like, Voronoi diagram, Delaunay triangulation, Gabriel graph, and relative neighborhood graphs to compute additional or Steiner points
  • Keywords
    computational geometry; parallel algorithms; search problems; trees (mathematics); Delaunay triangulation; Euclidean Steiner tree problem; Gabriel graph; Voronoi diagram; computational geometry; parallel local search; relative neighborhood graphs; Computational geometry; Computer science; Concurrent computing; Data mining; Explosions; Mathematics; Parallel processing; Polynomials; Robustness; Steiner trees;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, 2006. SNPD 2006. Seventh ACIS International Conference on
  • Conference_Location
    Las Vegas, NV
  • Print_ISBN
    0-7695-2611-X
  • Type

    conf

  • DOI
    10.1109/SNPD-SAWN.2006.7
  • Filename
    1640683
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2079506