Údaje o výsledku |
Identifikační kód | RIV/00216224:14330/13:00066369 |
Název v původním jazyce | Better algorithms for satisfiability problems for formulas of bounded rank-width |
Druh | J - Článek v odborném periodiku |
Jazyk | eng - angličtina |
Obor | IN - Informatika |
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í | Jimp - Článek v impaktovaném časopise evidovaném ve Web of Science |
Skupina oboru v hodnocení | 04 - Technické a informatické vědy |
Konkrétní způsob(y) hodnocení výsledku | Článek v impaktovaném časopise evidovaném ve Web of Science |
Bodové ohodnocení | 13,055 |
Faktor korekce | 86,1 % |
Body (upravené podle přílohy č. 8 Metodiky) | 11,243 |
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 | 100,0 % | 13,055 | 11,243 |
|
Tvůrci výsledku |
Počet tvůrců celkem | 3 |
Počet domácích tvůrců | 3 |
Tvůrce | Ganian Robert (státní příslušnost: US - Spojené státy americké; A - domácí tvůrce; vedidk: 6376290) |
Tvůrce | Hliněný Petr (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; vedidk: 7595646) |
Tvůrce | Obdržálek Jan (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; vedidk: 3294099) |
Údaje blíže specifikující výsledek |
Popis v původním jazyce | We provide a parameterized polynomial algorithm for the propositional model counting problem #SAT, the runtime of which is single-exponential in the rank-width of a formula. Previously, analogous algorithms have been known -- e.g.~[Fischer, Makowsky, and Ravve] -- with a single-exponential dependency on the clique-width of a formula. Our algorithm thus presents an exponential runtime improvement (since clique-width reaches up to exponentially higher values than rank-width), and can be of practical interest for small values of rank-width. We also provide an algorithm for the MAX-SAT problem along the same lines. |
Klíčová slova | propositional model counting; satisfiability; rank-width; clique-width; parameterized complexity |
Kód UT ISI | 000317267500005 |
Rozsah stran | 59-76 |
Název periodka | Fundamenta Informaticae |
ISSN | 0169-2968 |
Svazek periodika | 123 |
Číslo periodika v rámci uvedeného svazku | 1 |
Stát vydavatele periodika | NL - Nizozemsko |
Počet stran výsledku | 18 |
DOI výsledku | 10.3233/FI-2013-800 |
Údaje o tomto záznamu o výsledku |
Předkladatel | Masarykova univerzita / Fakulta informatiky |
Dodavatel | GA0 - Grantová agentura České republiky (GA ČR) |
Rok sběru | 2014 |
Systémové označení dodávky dat | RIV14-GA0-14330___/01:1 |
Specifikace | RIV/00216224:14330/13:00066369!RIV14-GA0-14330___ |
Kontrolní kód | [7F4150700843] |
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 | GAP202/11/0196 - Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů (2011-2013, GA0/GA) |