Journal article icon

Journal article

Fine-grained dichotomies for the Tutte Plane and Boolean #CSP

Abstract:

Jaeger et al. (Math Proc Camb Philos Soc 108(1):35–53, 1990) proved a dichotomy for the complexity of evaluating the Tutte polynomial at fixed points: the evaluation is #P-hard almost everywhere, and the remaining points admit polynomial-time algorithms. Dell, Husfeldt, and Wahlén (in: ICALP 2010, vol. 6198, pp. 426–437, Springer, Berlin, Heidelberg, 2010) and Husfeldt and Taslaman (in: IPEC 2010, vol. 6478, pp. 192–203, Springer, Berlin, Heidelberg, 2010) in combination with the results of C...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1007/s00453-018-0472-z

Authors


More by this author
Role:
Author
ORCID:
0000-0001-8955-0786
More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Oxford college:
Merton, Merton College
Department:
Unknown
Role:
Author
Publisher:
Springer Nature Publisher's website
Journal:
Algorithmica Journal website
Volume:
81
Issue:
2
Pages:
541-556
Publication date:
2018-06-22
Acceptance date:
2018-06-16
DOI:
EISSN:
1432-0541
ISSN:
0178-4617
Source identifiers:
1068875
Language:
English
Keywords:
Pubs id:
pubs:1068875
UUID:
uuid:24873dca-8cae-41f1-9d7e-6332846f86b8
Local pid:
pubs:1068875
Deposit date:
2019-10-31

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP