• DocumentCode
    985311
  • Title

    Efficient algorithm for common spanning tree problem

  • Author

    Schach, S.R.

  • Author_Institution
    University of Cape Town, Computer Science Department, Rondebosch, South Africa
  • Volume
    19
  • Issue
    9
  • fYear
    1983
  • Firstpage
    346
  • Lastpage
    347
  • Abstract
    Enumerating the spanning trees common to a pair of graphs is a problem which arises in symbolic circuit analysis. The algorithm presented here is between 350% and 26000% faster than the best algorithm previously published, and hence the computer analysis of circuits of a reasonable size is now feasible.
  • Keywords
    algorithm theory; circuit analysis computing; trees (mathematics); algorithm; circuit analysis computing; common spanning tree problem; symbolic circuit analysis; tree enumeration method;
  • fLanguage
    English
  • Journal_Title
    Electronics Letters
  • Publisher
    iet
  • ISSN
    0013-5194
  • Type

    jour

  • DOI
    10.1049/el:19830240
  • Filename
    4247681
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=985311