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

GANIAN, Robert, Petr HLINĚNÝ a Jan OBDRŽÁLEK. Better algorithms for satisfiability problems for formulas of bounded rank-width. Online. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). 2010. vyd. Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS, 2010, s. 73-83. ISBN 978-3-939897-23-1. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.73.

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í: 2010. vyd. Dagstuhl, Germany, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), od s. 73-83, 11 s. 2010.
• Nakladatel: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS

Další údaje

• Originální jazyk: angličtina
• Typ výsledku: Stať ve sborníku
• Obor: 10201 Computer sciences, information science, bioinformatics
• Stát vydavatele: Indie
• Utajení: není předmětem státního či obchodního tajemství
• Forma vydání: elektronická verze "online"
• WWW: DOI URL
• Kód RIV: RIV/00216224:14330/10:00045217
• Organizační jednotka: Fakulta informatiky
• ISBN: 978-3-939897-23-1
• ISSN: 1868-8969
• Doi: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.73
• UT WoS: 000310361000006
• Klíčová slova anglicky: propositional model counting; satisfiability; rank-width; clique-width; parameterized complexity
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

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

• GA201/08/0308, projekt VaV: Název: Využití strukturálních a "šířkových" parametrů v kombinatorice a algoritmické složitosti

Investor: Grantová agentura ČR, Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti

• GC201/09/J021, projekt VaV: Název: Strukturální teorie grafů a parametrizovaná složitost

Investor: Grantová agentura ČR, Strukturální teorie grafů a parametrizovaná složitost

• MSM0021622419, záměr: Název: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy

• MUNI/A/0914/2009, interní kód MU: Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Akronym: SV-FI MAV)

Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty

• MUNI/E/0059/2009, interní kód MU: Název: Parameterized Algorithms and Width measures on Graphs

Investor: Masarykova univerzita, Parameterized Algorithms and Width measures on Graphs, Kat. E - Podpora výzkumné činnosti studentů v oborech lékařství, zdravotnictví, přírodovědy a informatiky - rozvojový projekt + specifický výzkum