<div class="csl-bib-body">
<div class="csl-entry">Fichte, J., Hecher, M., Lodha, N., & Szeider, S. (2018). An SMT Approach to Fractional Hypertree Width. In J. Hooker (Ed.), <i>Principles and Practice of Constraint Programming, 24th International Conference, CP 2018</i> (pp. 109–127). Springer-Verlag. https://doi.org/10.1007/978-3-319-98334-9_8</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/86758
-
dc.description.abstract
Bounded fractional hypertree width ( Open image in new window ) is the most general known structural property that guarantees polynomial-time solvability of the constraint satisfaction problem. Bounded Open image in new window generalizes other structural properties like bounded induced width and bounded hypertree width.
We propose, implement and test the first practical algorithm for computing the Open image in new window and its associated structural decomposition. We provide an extensive empirical evaluation of our method on a large class of benchmark instances which also provides a comparison with known exact decomposition methods for hypertree width. Our approach is based on an efficient encoding of the decomposition problem to SMT (SAT modulo Theory) with Linear Arithmetic as implemented in the SMT solver Open image in new window . The encoding is further strengthened by preprocessing and symmetry breaking methods. Our experiments show (i) that Open image in new window can indeed be computed exactly for a wide range of benchmark instances, and (ii) that state-of-the art SMT techniques can be successfully applied for structural decomposition.
-
dc.description.sponsorship
Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.language.iso
en
-
dc.publisher
Springer-Verlag
-
dc.relation.ispartofseries
Lecture Notes in Computer Science
-
dc.subject
SMT
-
dc.subject
Approach Fractional Hypertree Width
-
dc.title
An SMT Approach to Fractional Hypertree Width
en
dc.type
Konferenzbeitrag
de
dc.type
Inproceedings
en
dc.relation.publication
Principles and Practice of Constraint Programming, 24th International Conference, CP 2018
-
dc.relation.isbn
978-3-319-98334-9
-
dc.relation.doi
10.1007/978-3-319-98334-9
-
dc.relation.issn
0302-9743
-
dc.description.startpage
109
-
dc.description.endpage
127
-
dc.relation.grantno
Y 698-N23
-
dc.type.category
Full-Paper Contribution
-
dc.relation.eissn
1611-3349
-
tuw.booktitle
Principles and Practice of Constraint Programming, 24th International Conference, CP 2018
-
tuw.book.ispartofseries
Lecture Notes in Computer Science
-
tuw.relation.publisher
Springer
-
tuw.relation.publisherplace
Cham
-
tuw.project.title
START
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publication.orgunit
E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
tuw.publisher.doi
10.1007/978-3-319-98334-9_8
-
dc.description.numberOfPages
19
-
tuw.event.name
24th International Conference on Principles and Practice of Constraint Programming (CP 2018)
-
tuw.event.startdate
27-08-2018
-
tuw.event.enddate
31-08-2018
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Lille
-
tuw.event.country
FR
-
tuw.event.presenter
Fichte, Johannes
-
wb.sciencebranch
Informatik
-
wb.sciencebranch.oefos
1020
-
wb.facultyfocus
Logic and Computation (LC)
-
wb.facultyfocus
Logic and Computation (LC)
-
wb.facultyfocus.faculty
E180
-
item.fulltext
no Fulltext
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.cerifentitytype
Publications
-
item.openairetype
conference paper
-
item.grantfulltext
none
-
item.languageiso639-1
en
-
crisitem.author.dept
E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
crisitem.author.dept
E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
crisitem.author.dept
E192-04 - Forschungsbereich Formal Methods in Systems Engineering
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity