Backdoors into Heterogeneous Classes of SAT and CSP (2014)výskyt výsledku
| Identifikační kód | RIV/00216224:14330/14:00077721 |
|---|---|
| Název v anglickém jazyce | Backdoors into Heterogeneous Classes of SAT and CSP |
| Druh | D - Článek ve sborníku |
| Jazyk | eng - angličtina |
| Obor - skupina | I - Informatika |
| Obor | IN - Informatika |
| Rok uplatnění | 2014 |
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
| Počet výskytů výsledku | 1 |
| Počet tvůrců celkem | 5 |
| Počet domácích tvůrců | 1 |
| Výčet všech uvedených jednotlivých tvůrců | Serge Gaspers (státní příslušnost: LU - Lucemburské velkovévodství) Sebastian Ordyniak (státní příslušnost: DE - Spolková republika Německo, domácí tvůrce: A) Stefan Szeider (státní příslušnost: AT - Rakouská republika) Neelhara Misra (státní příslušnost: IN - Indická republika) Stanislav Živný (státní příslušnost: CZ - Česká republika) |
| Popis výsledku v anglickém jazyce | Backdoor sets represent clever reasoning shortcuts through the search space for SAT and CSP. By instantiating the backdoor variables one reduces the given instance to several easy instances that belong to a tractable class.The overall time needed to solve the instance is exponential in the size of the backdoor set, hence it is a challenging problem to find a small backdoor set if one exists; over the last years this problem has been subject of intensive research. In this paper we extend the classical notion of a strong backdoor set by allowing that different instantiations of the backdoor variables result in instances that belong to different base classes; the union of the base classes forms a heterogeneous base class. Backdoor sets to heterogeneous base classes can be much smaller than backdoor sets to homogeneous ones, hence they are much more desirable but possibly harder to find. |
| Klíčová slova oddělená středníkem | parameterized complexity; satisfiability; constraint satisfaction; strong backdoor; polymorphism |
| Stránka www, na které se nachází výsledek | - |
Údaje o výsledku v závislosti na druhu výsledku
| Název sborníku | AAAI Press |
|---|---|
| ISBN | 9781577356806 |
| ISSN | - |
| Počet stran výsledku | 7 |
| Strana od-do | 2652-2658 |
| Název nakladatele | AAAI Press |
| Místo vydání | Quebec |
| Místo konání akce | Quebec |
| Datum konání akce | 22.07.2014 |
| Typ akce podle státní příslušnosti účastníků | WRD - Celosvětová |
| Kód UT WoS článku podle Web of Science | - |
Ostatní informace o výsledku
| Předkladatel | Masarykova univerzita / Fakulta informatiky |
|---|---|
| Dodavatel | MSM - Ministerstvo školství, mládeže a tělovýchovy (MŠMT) |
| Rok sběru | 2015 |
| Specifikace | RIV/00216224:14330/14:00077721!RIV15-MSM-14330___ |
| Datum poslední aktualizace výsledku | 29.05.2015 |
| Kontrolní číslo | 152395018 |
Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl
| Projekt podporovaný MŠMT v programu EE | EE2.3.30.0009 - Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci (2012 - 2015) |
|---|