• DocumentCode
    889999
  • Title

    A near-optimal heuristic algorithm for single-flow routing

  • Author

    Liu, L.C. ; Du, H.C.

  • Author_Institution
    Dept. of Comput. Sci., Univ. of Minnesota, Minneapolis, MN, USA
  • Volume
    38
  • Issue
    4
  • fYear
    1989
  • fDate
    4/1/1989 12:00:00 AM
  • Firstpage
    603
  • Lastpage
    608
  • Abstract
    The authors obtain a tighter lower bound on the street congestion of optimal realizations. Then a heuristic algorithm based on necessary and sufficient conditions of optimality is proposed. Although it cannot be guaranteed that this algorithm always generates optimal realizations, it indeed generates optimal realizations for all the 60 test instances with which they experimented. This algorithm is also shown to be time efficient
  • Keywords
    circuit layout CAD; near-optimal heuristic algorithm; necessary and sufficient conditions; optimality; single-flow routing; tighter lower bound; Arithmetic; Concurrent computing; Counting circuits; Equations; Flip-flops; Heuristic algorithms; Logic; Registers; Routing; Systolic arrays;
  • fLanguage
    English
  • Journal_Title
    Computers, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9340
  • Type

    jour

  • DOI
    10.1109/12.21154
  • Filename
    21154
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=889999