Title
Efficient Algorithms For Computing Matching And Chromatic Polynomials On Series-Parallel Graphs
Abstract
We present efficient algorithms for computing the matching polynomial and chromatic polynomial of a series-parallel graph in O(n3) and O(n2) time respectively. Our algorithm for computing the matching polynomial generalizes an existing result from [5] and the chromatic polynomial algorithm improves the result in [4] from O(n4) time.
Publication Date
1-1-1992
Publication Title
Proceedings - ICCI 1992: 4th International Conference on Computing and Information
Number of Pages
42-45
Document Type
Article; Proceedings Paper
Identifier
scopus
Personal Identifier
scopus
DOI Link
https://doi.org/10.1109/ICCI.1992.227709
Copyright Status
Unknown
Socpus ID
84881072176 (Scopus)
Source API URL
https://api.elsevier.com/content/abstract/scopus_id/84881072176
STARS Citation
Chandrasekharan, N. and Hannenhalli, Sridhar, "Efficient Algorithms For Computing Matching And Chromatic Polynomials On Series-Parallel Graphs" (1992). Scopus Export 1990s. 1017.
https://stars.library.ucf.edu/scopus1990/1017