Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{1523797,
author = {Ganian, Robert and Kim, Eunjung and Slivovsky, Friedrich and Szeider, Stefan},
address = {USA},
booktitle = {IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI)},
doi = {http://dx.doi.org/10.1109/ICTAI.2018.00115},
editor = {Lefteri H. Tsoukalas, Eric Gregoire, Miltiadis Alamaniotis},
keywords = {Sum of Products; Constraint Satisfaction; Boolean Satisfiability; Parameterized Complexity},
howpublished = {elektronická verze "online"},
language = {eng},
location = {USA},
isbn = {978-1-5386-7449-9},
pages = {733-737},
publisher = {IEEE},
title = {Sum-of-Products with Default Values: Algorithms and Complexity Results},
year = {2018}
}
TY - JOUR
ID - 1523797
AU - Ganian, Robert - Kim, Eunjung - Slivovsky, Friedrich - Szeider, Stefan
PY - 2018
TI - Sum-of-Products with Default Values: Algorithms and Complexity Results
PB - IEEE
CY - USA
SN - 9781538674499
KW - Sum of Products
KW - Constraint Satisfaction
KW - Boolean Satisfiability
KW - Parameterized Complexity
N2 - Weighted Counting for Constraint Satisfaction with Default Values (#CSPD) is a powerful special case of the sum-of-products problem that admits succinct encodings of #CSP, #SAT, and inference in probabilistic graphical models. We investigate #CSPD under the fundamental parameter of incidence treewidth (i.e., the treewidth of the incidence graph of the constraint hypergraph). We show that if the incidence treewidth is bounded, then #CSPD can be solved in polynomial time. More specifically, we show that the problem is fixed-parameter tractable for the combined parameter incidence treewidth, domain size, and support size (the maximum number of non-default tuples in a constraint), generalizing a known result on the fixed-parameter tractability of #CSPD under the combined parameter primal treewidth and domain size. We further prove that the problem is not fixed-parameter tractable if any of the three components is dropped from the parameterization.
ER -
GANIAN, Robert, Eunjung KIM, Friedrich SLIVOVSKY a Stefan SZEIDER. Sum-of-Products with Default Values: Algorithms and Complexity Results. Online. In Lefteri H. Tsoukalas, Eric Gregoire, Miltiadis Alamaniotis. \textit{IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI)}. USA: IEEE, 2018, s.~733-737. ISBN~978-1-5386-7449-9. Dostupné z: https://dx.doi.org/10.1109/ICTAI.2018.00115.
|
