Journal article icon

Journal article

Complexity analysis of generalized and fractional hypertree decompositions

Abstract:

Hypertree decompositions (HDs), as well as the more powerful generalized hypertree decompositions (GHDs), and the yet more general fractional hypertree decompositions (FHDs) are hypergraph decomposition methods successfully used for answering conjunctive queries and for solving constraint satisfaction problems. Every hypergraph H has a width relative to each of these methods: its hypertree width hw(H), its generalized hypertree width ghw(H), and its fractional hypertree width fhw(H), respe...

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

Actions


Access Document


Files:
Publisher copy:
10.1145/3457374

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More from this funder
Name:
Royal Society
Grant:
RP\R1\201074
Publisher:
Association for Computing Machinery
Journal:
Journal of the ACM More from this journal
Volume:
68
Issue:
5
Article number:
38
Publication date:
2021-09-13
Acceptance date:
2021-03-01
DOI:
EISSN:
1557-735X
ISSN:
0004-5411

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