Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{1648256,
author = {Ganian, Robert and Ordyniak, Sebastian and Szeider, Stefan},
address = {USA},
booktitle = {Principles and Practice of Constraint Programming - 25th International Conference},
doi = {http://dx.doi.org/10.1007/978-3-030-30048-7_12},
editor = {Thomas Schiex and Simon de Givry},
keywords = {Parameterized Complexity},
howpublished = {elektronická verze "online"},
language = {eng},
location = {USA},
isbn = {978-3-030-30047-0},
pages = {195-212},
publisher = {Springer},
title = {A Join-Based Hybrid Parameter for Constraint Satisfaction},
url = {https://link.springer.com/chapter/10.1007%2F978-3-030-30048-7_12},
year = {2019}
}
TY - JOUR
ID - 1648256
AU - Ganian, Robert - Ordyniak, Sebastian - Szeider, Stefan
PY - 2019
TI - A Join-Based Hybrid Parameter for Constraint Satisfaction
PB - Springer
CY - USA
SN - 9783030300470
KW - Parameterized Complexity
UR - https://link.springer.com/chapter/10.1007%2F978-3-030-30048-7_12
L2 - https://link.springer.com/chapter/10.1007%2F978-3-030-30048-7_12
N2 - We propose joinwidth, a new complexity parameter for the Constraint Satisfaction Problem (CSP). The definition of joinwidth is based on the arrangement of basic operations on relations (joins, projections, and pruning), which inherently reflects the steps required to solve the instance. We use joinwidth to obtain polynomial-time algorithms (if a corresponding decomposition is provided in the input) as well as fixed-parameter algorithms (if no such decomposition is provided) for solving the CSP. Joinwidth is a hybrid parameter, as it takes both the graphical structure as well as the constraint relations that appear in the instance into account. It has, therefore, the potential to capture larger classes of tractable instances than purely structural parameters like hypertree width and the more general fractional hypertree width (fhtw). Indeed, we show that any class of instances of bounded fhtw also has bounded joinwidth, and that there exist classes of instances of bounded joinwidth and unbounded fhtw, so bounded joinwidth properly generalizes bounded fhtw. We further show that bounded joinwidth also properly generalizes several other known hybrid restrictions, such as fhtw with degree constraints and functional dependencies. In this sense, bounded joinwidth can be seen as a unifying principle that explains the tractability of several seemingly unrelated classes of CSP instances.
ER -
GANIAN, Robert, Sebastian ORDYNIAK a Stefan SZEIDER. A Join-Based Hybrid Parameter for Constraint Satisfaction. Online. In Thomas Schiex and Simon de Givry. \textit{Principles and Practice of Constraint Programming - 25th International Conference}. USA: Springer, 2019, s.~195-212. ISBN~978-3-030-30047-0. Dostupné z: https://dx.doi.org/10.1007/978-3-030-30048-7\_{}12.
|
