D 2016

Backdoors to Tractable Valued CSP

GANIAN, Robert, M.S. RAMANUJAN a Stefan SZEIDER

Základní údaje

Originální název

Backdoors to Tractable Valued CSP

Autoři

GANIAN, Robert (203 Česká republika, garant, domácí), M.S. RAMANUJAN (360 Indonésie) a Stefan SZEIDER (40 Rakousko)

Vydání

CHAM, PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING, CP 2016, od s. 233-250, 18 s. 2016

Nakladatel

SPRINGER INT PUBLISHING AG

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/16:00093942

Organizační jednotka

Fakulta informatiky

ISBN

978-3-319-44952-4

ISSN

DOI

UT WoS

000389019700017

Klíčová slova anglicky

CSP; backdoors

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 27. 4. 2017 07:08, RNDr. Pavel Šmerk, Ph.D.

Anotace

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.