• DocumentCode
    3256652
  • Title

    Efficient algorithms for computing matching and chromatic polynomials on series-parallel graphs

  • Author

    Chandrasekharan, N. ; Hannenhalli, Sridhar

  • Author_Institution
    Dept. of Comput. Sci., Univ. of Central Florida, Orlando, FL, USA
  • fYear
    1992
  • fDate
    28-30 May 1992
  • Firstpage
    42
  • Lastpage
    45
  • Abstract
    The authors present efficient algorithms for computing the matching polynomial and chromatic polynomial of a series-parallel graph in O(n3) and O(n2) time respectively. Their algorithm for computing the matching polynomial generalizes an existing result from Lovasz, Plummer (1986) and the chromatic polynomial algorithm improves the result given by Hunt, Ravi, Stearn (1988) from O(n4) time
  • Keywords
    computational complexity; graph colouring; graph theory; polynomials; chromatic polynomials; matching polynomial; series-parallel graphs; Computer science; Polynomials; Terminology; Tree data structures; Tree graphs;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computing and Information, 1992. Proceedings. ICCI '92., Fourth International Conference on
  • Conference_Location
    Toronto, Ont.
  • Print_ISBN
    0-8186-2812-X
  • Type

    conf

  • DOI
    10.1109/ICCI.1992.227709
  • Filename
    227709
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3256652