J 2013

Better algorithms for satisfiability problems for formulas of bounded rank-width

GANIAN, Robert, Petr HLINĚNÝ a Jan OBDRŽÁLEK

Základní údaje

Originální název

Better algorithms for satisfiability problems for formulas of bounded rank-width

Autoři

GANIAN, Robert (840 Spojené státy, domácí), Petr HLINĚNÝ (203 Česká republika, garant, domácí) a Jan OBDRŽÁLEK (203 Česká republika, domácí)

Vydání

Fundamenta Informaticae, Poland, IOS Press, The Netherlands, 2013, 0169-2968

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Nizozemské království

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.479

Kód RIV

RIV/00216224:14330/13:00066369

Organizační jednotka

Fakulta informatiky

DOI

UT WoS

000317267500005

Klíčová slova anglicky

propositional model counting; satisfiability; rank-width; clique-width; parameterized complexity

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 31. 3. 2014 13:21, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

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.

Návaznosti

GAP202/11/0196, projekt VaV
Název: Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů
Investor: Grantová agentura ČR, Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů