Backdoors to q-Horn (2013)výskyt výsledku
| Identifikační kód | RIV/00216224:14330/13:00072816 |
|---|---|
| Název v anglickém jazyce | Backdoors to q-Horn |
| Druh | D - Článek ve sborníku |
| Jazyk | eng - angličtina |
| Obor - skupina | B - Fyzika a matematika |
| Obor | BD - Teorie informace |
| Rok uplatnění | 2013 |
| 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ů | Sebastian Ordyniak (státní příslušnost: DE - Spolková republika Německo, domácí tvůrce: A) M S Ramanujan (státní příslušnost: IN - Indická republika) Stefan Szeider (státní příslušnost: AT - Rakouská republika) Serge Gaspers (státní příslušnost: LU - Lucemburské velkovévodství) Saket Saurabh (státní příslušnost: IN - Indická republika) |
| Popis výsledku v anglické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 thatsatisfiability 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 oddělená středníkem | satisfiability; backdoors; parameterized complexity |
| Stránka www, na které se nachází výsledek | - |
| DOI výsledku | 10.4230/LIPIcs.STACS.2013.67 |
Údaje o výsledku v závislosti na druhu výsledku
| Název sborníku | LIPIcs |
|---|---|
| ISBN | 9783939897507 |
| ISSN | 1868-8969 |
| Počet stran výsledku | 13 |
| Strana od-do | 67-79 |
| Název nakladatele | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik |
| Místo vydání | Germany |
| Místo konání akce | Kiel, Germany |
| Datum konání akce | 2013 |
| 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 | 2014 |
| Specifikace | RIV/00216224:14330/13:00072816!RIV14-MSM-14330___ |
| Datum poslední aktualizace výsledku | 29.05.2014 |
| Kontrolní číslo | 56540817 |
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) |
|---|