Detailed Information on Publication Record
2016
Backdoors to Tractable Valued CSP
GANIAN, Robert, M.S. RAMANUJAN and Stefan SZEIDERBasic 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
Language
English
Type of outcome
Stať ve sborníku
Field of Study
10201 Computer sciences, information science, bioinformatics
Confidentiality degree
není předmětem státního či obchodního tajemství
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
UT WoS
000389019700017
Keywords in English
CSP; backdoors
Tags
International impact, Reviewed
Změněno: 27/4/2017 07:08, RNDr. Pavel Šmerk, Ph.D.
Abstract
V originále
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.