• DocumentCode
    2663908
  • Title

    A new efficient approximation algorithm for the Steiner tree problem in rectilinear graphs

  • Author

    Mastumoto, Tadashi ; Saigan, Naoshi ; Tsuji, Koukichi

  • Author_Institution
    Dept. of Electr. & Electron. Eng., Fukui Univ., Japan
  • fYear
    1990
  • fDate
    1-3 May 1990
  • Firstpage
    2873
  • Abstract
    The Steiner tree problem in a grid graph with all edges having weight 1 is considered. For a given finite set P of the generating points in the grid graph, an approximation algorithm using properties of the Delaunay net and the optimum Steiner tree with three generating points is proposed. It is shown that the complexity of this algorithm does not depend on the number of nodes of a grid graph and is O(k2), where k is the number of the generating points of P. lt is shown that this algorithm always generates the optimum Steiner tree for k⩽4
  • Keywords
    computational complexity; network topology; trees (mathematics); Delaunay net; Steiner tree problem; approximation algorithm; grid graph; rectilinear graphs; Approximation algorithms; Mesh generation; Polynomials; Steiner trees; Tree graphs; Very large scale integration;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Circuits and Systems, 1990., IEEE International Symposium on
  • Conference_Location
    New Orleans, LA
  • Type

    conf

  • DOI
    10.1109/ISCAS.1990.112610
  • Filename
    112610
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2663908