• DocumentCode
    912721
  • Title

    An Approximation Problem for the Multi-Via Assignment Problem

  • Author

    Gonzalez, Teofilo F.

  • Author_Institution
    Department of Computer Science, The University of California, Santa Barbara, CA, USA
  • Volume
    3
  • Issue
    4
  • fYear
    1984
  • fDate
    10/1/1984 12:00:00 AM
  • Firstpage
    257
  • Lastpage
    264
  • Abstract
    We consider the multi-via assignment problem for multilayered printed circuit board routing. An efficient approximation algorithm for this problem is presented. The algorithm is of (low) polynomial time complexity and guarantees solutions with no more than 3 * OPT via columns, where OPT is the number of via columns in an optimal solution. Several issues relating to the computational complexity of via and multi-via assignment problems are also discussed.
  • Keywords
    Computer science; Integrated circuit interconnections; NP-hard problem; Nonhomogeneous media; Optimized production technology; Pins; Printed circuits; Routing; Silicon; Wires;
  • fLanguage
    English
  • Journal_Title
    Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0278-0070
  • Type

    jour

  • DOI
    10.1109/TCAD.1984.1270084
  • Filename
    1270084
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=912721