Efficient algorithms for computing matching and chromatic polynomials on series-parallel graphs
| Title | Efficient algorithms for computing matching and chromatic polynomials on series-parallel graphs |
| Publication Type | Conference Proceedings |
| Year of Conference | 1992 |
| Authors | Chandrasekharan N., Hannenhalli S |
| Conference Name | Fourth International Conference on Computing and Information, 1992. Proceedings. ICCI '92 |
| Date Published | 1992 |
| Publisher | IEEE |
| ISBN Number | 0-8186-2812-X |
| Keywords | chromatic polynomials, computational complexity, Computer science, graph colouring, graph theory, matching polynomial, Polynomials, series-parallel graphs, Terminology, Tree data structures, Tree graphs |
| 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 |