Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1376014, author = {Ganian, Robert and Ramanujan, M.S. and Szeider, Stefan}, address = {CHAM}, booktitle = {PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING, CP 2016}, doi = {http://dx.doi.org/10.1007/978-3-319-44953-1_16}, editor = {Rueher, M}, keywords = {CSP; backdoors}, howpublished = {tištěná verze "print"}, language = {eng}, location = {CHAM}, isbn = {978-3-319-44952-4}, pages = {233-250}, publisher = {SPRINGER INT PUBLISHING AG}, title = {Backdoors to Tractable Valued CSP}, year = {2016} }
TY - JOUR ID - 1376014 AU - Ganian, Robert - Ramanujan, M.S. - Szeider, Stefan PY - 2016 TI - Backdoors to Tractable Valued CSP PB - SPRINGER INT PUBLISHING AG CY - CHAM SN - 9783319449524 KW - CSP KW - backdoors N2 - We extend the notion of a strong backdoor from the CSP setting to the Valued CSP setting (VCSP, for short). This provides a means for augmenting a class of tractable VCSP instances to instances that are outside the class but of small distance to the class, where the distance is measured in terms of the size of a smallest backdoor. We establish that VCSP is fixed-parameter tractable when parameterized by the size of a smallest backdoor into every tractable class of VCSP instances characterized by a (possibly infinite) tractable valued constraint language of finite arity and finite domain. We further extend this fixed-parameter tractability result to so-called "scattered classes" of VCSP instances where each connected component may belong to a different tractable class. ER -
GANIAN, Robert, M.S. RAMANUJAN and Stefan SZEIDER. Backdoors to Tractable Valued CSP. In Rueher, M. \textit{PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING, CP 2016}. CHAM: SPRINGER INT PUBLISHING AG, 2016, p.~233-250. ISBN~978-3-319-44952-4. Available from: https://dx.doi.org/10.1007/978-3-319-44953-1\_{}16.
|