Chromatic, flow and reliability polynomials: The complexity of their coefficients
We study the complexity of computing the coefficients of three classical polynomials, namely the chromatic, flow and reliability polynomials of a graph. Each of these is a specialization of the Tutte polynomial ∑tijxiyj. It is shown that, unless NP = RP, many of the relevant coefficients do not even...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2002
|