Journal article
Chromatic, flow and reliability polynomials: The complexity of their coefficients
- Abstract:
-
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 have good randomized approximation schemes. We consider the quasi-order induced by approximation reducibility and highlight the pivotal position of the coefficient t10 = t01, otherwise known as th...
Expand abstract
- Publication status:
- Published
Actions
Authors
Bibliographic Details
- Journal:
- COMBINATORICS PROBABILITY and COMPUTING
- Volume:
- 11
- Issue:
- 4
- Pages:
- 403-426
- Publication date:
- 2002-07-01
- DOI:
- EISSN:
-
1469-2163
- ISSN:
-
0963-5483
- Source identifiers:
-
17243
Item Description
- Language:
- English
- Pubs id:
-
pubs:17243
- UUID:
-
uuid:ac77448c-7227-4b4f-aa2f-f6098a26a1ca
- Local pid:
- pubs:17243
- Deposit date:
- 2012-12-19
Terms of use
- Copyright date:
- 2002
If you are the owner of this record, you can report an update to it here: Report update to this record