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://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; Petr HLINĚNÝ ORCID a Jan OBDRŽÁLEK

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

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"

Odkazy

DOI, URL

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/10:00045217

Organizační jednotka

Fakulta informatiky

ISBN

978-3-939897-23-1

ISSN

DOI

https://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

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

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