TY - Generic
T1 - Efficient algorithms for computing matching and chromatic polynomials on series-parallel graphs
T2 - Fourth International Conference on Computing and Information, 1992. Proceedings. ICCI '92
Y1 - 1992
A1 - Chandrasekharan, N.
A1 - Sridhar Hannenhalli
KW - chromatic polynomials
KW - computational complexity
KW - Computer science
KW - graph colouring
KW - graph theory
KW - matching polynomial
KW - Polynomials
KW - series-parallel graphs
KW - Terminology
KW - Tree data structures
KW - Tree graphs
AB - 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
JA - Fourth International Conference on Computing and Information, 1992. Proceedings. ICCI '92
PB - IEEE
SN - 0-8186-2812-X
ER -