| Údaje o výsledku |
| Identifikační kód | RIV/00216224:14330/13:00072816 |
| Název v původním jazyce | Backdoors to q-Horn |
| Druh | D - Článek ve sborníku |
| Jazyk | eng - angličtina |
| Obor | BD - Teorie informace |
| Rok uplatnění | 2013 |
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů |
| Počet výskytů výsledku | 1 |
| Údaje z Hodnocení výsledků výzkumných organizací 2014 |
| Výsledek byl hodnocen v Pilíři I |
| Rozsah vyřazení výsledku | Tento výskyt výsledku není vyřazen |
| Zařazení výsledku v hodnocení | D - Článek ve sborníku |
| Skupina oboru v hodnocení | 04 - Technické a informatické vědy |
| Konkrétní způsob(y) hodnocení výsledku | Článek ve sborníku evidovaném v databázi Scopus |
| Bodové ohodnocení | 8,000 |
| Faktor korekce | 50,1 % |
| Body (upravené podle přílohy č. 8 Metodiky) | 4,009 |
| Rozdělení výsledku mezi předkladatele |
| Organizace | Výzkumná organizace? | Podíl | Body | Body (upravené podle přílohy č. 8 Metodiky) |
|---|
| Masarykova univerzita / Fakulta informatiky | ano | 33,3 % | 2,667 | 1,336 |
|
| Tvůrci výsledku |
| Počet tvůrců celkem | 5 |
| Počet domácích tvůrců | 1 |
| Tvůrce | Ordyniak Sebastian (státní příslušnost: DE - Spolková republika Německo; A - domácí tvůrce) |
| Tvůrce | Ramanujan M S (státní příslušnost: IN - Indická republika) |
| Tvůrce | Szeider Stefan (státní příslušnost: AT - Rakouská republika) |
| Tvůrce | Gaspers Serge (státní příslušnost: LU - Lucemburské velkovévodství) |
| Tvůrce | Saurabh Saket (státní příslušnost: IN - Indická republika) |
| Údaje blíže specifikující výsledek |
| Popis v původním jazyce | The class q-Horn, introduced by Boros, Crama and Hammer in 1990, is one of the largest known classes of propositional CNF fomulas for which satisfiability decision is polynomial. This class properly contains the fundamental classes of Horn and 2CNF formulas as well as the class of renamable (or disguised) Horn formulas. In this paper we gradually extend this class such that its favorable algorithmic properties can be made accessible to formulas that are outside but ``close'' to this class. We show that satisfiability decision is fixed-parameter tractable parameterized by the distance of the given formula from q-Horn. The distance is measured as the smallest number of variables that we need to delete from F in order to get a q-Horn formula, i.e., the size of a smallest deletion backdoor set into the class q-Horn. |
| Klíčová slova | satisfiability; backdoors; parameterized complexity |
| Název sborníku | LIPIcs |
| Rozsah stran | 67-79 |
| Forma vydání | P - Tištěná verze „print“ |
| ISSN | 1868-8969 |
| Počet stran výsledku | 13 |
| ISBN | 9783939897507 |
| Název nakladatele | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik |
| Místo vydání | Germany |
| Místo konání akce | Kiel, Germany |
| Rok konání akce | 2013 |
| Typ akce podle státní příslušnoti účastníků | WRD - Světová |
| DOI výsledku | 10.4230/LIPIcs.STACS.2013.67 |
| Údaje o tomto záznamu 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 | 2014 |
| Systémové označení dodávky dat | RIV14-MSM-14330___/01:1 |
| Specifikace | RIV/00216224:14330/13:00072816!RIV14-MSM-14330___ |
| Kontrolní kód | [D024B001777B] |
| Jiný výskyt tohoto výsledku se v RIV nenachází |
| Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl |
| Projekt | EE2.3.30.0009 - Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci (2012-2015, MSM/EE) |