Conference item icon

Conference item

General and fractional hypertree decompositions: hard and easy cases

Abstract:

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

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted Manuscript

Actions


Access Document


Files:
Publisher copy:
10.1145/3196959.3196962

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Oxford college:
St Johns College
Pichler, R More by this author
Publisher:
Association for Computing Machinery Publisher's website
Pages:
17-32
Publication date:
2018-05-27
DOI:
Pubs id:
pubs:657219
URN:
uri:dc037eb9-6fdf-4ca1-b60b-7cb069863da4
UUID:
uuid:dc037eb9-6fdf-4ca1-b60b-7cb069863da4
Local pid:
pubs:657219
ISBN:
978-1-4503-4706-8
Keywords:

Terms of use


Metrics



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

TO TOP