GANIAN, Robert, M.S. RAMANUJAN and Stefan SZEIDER. Backdoors to Tractable Valued CSP. In Rueher, M. 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.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Backdoors to Tractable Valued CSP
Authors GANIAN, Robert (203 Czech Republic, guarantor, belonging to the institution), M.S. RAMANUJAN (360 Indonesia) and Stefan SZEIDER (40 Austria).
Edition CHAM, PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING, CP 2016, p. 233-250, 18 pp. 2016.
Publisher SPRINGER INT PUBLISHING AG
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Confidentiality degree is not subject to a state or trade secret
Publication form printed version "print"
Impact factor Impact factor: 0.402 in 2005
RIV identification code RIV/00216224:14330/16:00093942
Organization unit Faculty of Informatics
ISBN 978-3-319-44952-4
ISSN 0302-9743
Doi http://dx.doi.org/10.1007/978-3-319-44953-1_16
UT WoS 000389019700017
Keywords in English CSP; backdoors
Tags core_A, firank_A
Tags International impact, Reviewed
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 27/4/2017 07:08.
Abstract
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.
PrintDisplayed: 25/4/2024 08:51