RIV/00216224:14330/13:00066369 - Better algorithms for satisfiability problems for formulas of bounded rank-width (2013)

Údaje o výsledku
Identifikační kódRIV/00216224:14330/13:00066369
Název v původním jazyceBetter algorithms for satisfiability problems for formulas of bounded rank-width
DruhJ - Článek v odborném periodiku
Jazykeng - angličtina
OborIN - 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ýsledku1
Údaje z Hodnocení výsledků výzkumných organizací 2014
Výsledek byl hodnocen v Pilíři I
Rozsah vyřazení výsledkuTento 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 korekce86,1 %
Body (upravené podle přílohy č. 8 Metodiky)11,243
Rozdělení výsledku mezi předkladatele
OrganizaceVýzkumná organizace?PodílBodyBody (upravené podle přílohy č. 8 Metodiky)
Masarykova univerzita / Fakulta informatikyano100,0 %13,05511,243
Tvůrci výsledku
Počet tvůrců celkem3
Počet domácích tvůrců3
TvůrceGanian Robert (státní příslušnost: US - Spojené státy americké; A - domácí tvůrce; vedidk: 6376290)
TvůrceHliněný Petr (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; vedidk: 7595646)
TvůrceObdržá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 jazyceWe 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á slovapropositional model counting; satisfiability; rank-width; clique-width; parameterized complexity
Kód UT ISI000317267500005
Rozsah stran59-76
Název periodkaFundamenta Informaticae
ISSN0169-2968
Svazek periodika123
Číslo periodika v rámci uvedeného svazku1
Stát vydavatele periodikaNL - Nizozemsko
Počet stran výsledku18
DOI výsledku10.3233/FI-2013-800
Údaje o tomto záznamu o výsledku
PředkladatelMasarykova univerzita / Fakulta informatiky
DodavatelGA0 - Grantová agentura České republiky (GA ČR)
Rok sběru2014
Systémové označení dodávky datRIV14-GA0-14330___/01:1
SpecifikaceRIV/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
ProjektGAP202/11/0196 - Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů (2011-2013, GA0/GA)