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

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Better algorithms for satisfiability problems for formulas of bounded rank-width Goto Sponge Distinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	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. 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. (en)
Title	Better algorithms for satisfiability problems for formulas of bounded rank-width Better algorithms for satisfiability problems for formulas of bounded rank-width (en)
skos:prefLabel	Better algorithms for satisfiability problems for formulas of bounded rank-width Better algorithms for satisfiability problems for formulas of bounded rank-width (en)
skos:notation	RIV/00216224:14330/10:00045217!RIV11-GA0-14330___
http://linked.open...avai/riv/aktivita	O P S Z
http://linked.open...avai/riv/aktivity	O, P(GA201/08/0308), P(GC201/09/J021), S, Z(MSM0021622419)
http://linked.open...vai/riv/dodaniDat	2011
http://linked.open...aciTvurceVysledku	Obdržálek, Jan Ganian, Robert Hliněný, Petr
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Masarykova univerzita / Fakulta informatiky
http://linked.open...dnocenehoVysledku	248651
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/10:00045217
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	propositional model counting; satisfiability; rank-width; clique-width; parameterized complexity (en)
http://linked.open.../riv/klicoveSlovo	parameterized complexity propositional model counting satisfiability clique-width rank-width
http://linked.open...ontrolniKodProRIV	[3E21A3F341A9]
http://linked.open...v/mistoKonaniAkce	Chennai, India
http://linked.open...i/riv/mistoVydani	Dagstuhl, Germany
http://linked.open...i/riv/nazevZdroje	IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	3 (xsd:int)
http://linked.open...cetTvurcuVysledku	3 (xsd:int)
http://linked.open...vavai/riv/projekt	Structural graph theory and parameterized complexity Utilization of structural and %22Width%22 parameters in combinatorics and algorithmic complexity
http://linked.open...UplatneniVysledku	2010
http://linked.open...iv/tvurceVysledku	Ganian, Robert Hliněný, Petr Obdržálek, Jan
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open...ain/vavai/riv/wos	000000
http://linked.open.../riv/zahajeniAkce	2010-01-01 (xsd:date)
http://linked.open...n/vavai/riv/zamer	Highly Parallel and Distributed Computing Systems
issn	1868-8969
number of pages	11 (xsd:int)
http://purl.org/ne...btex#hasPublisher	Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS
https://schema.org/isbn	978-3-939897-23-1
http://localhost/t...ganizacniJednotka	14330
is http://linked.open...avai/riv/vysledek of	Better algorithms for satisfiability problems for formulas of bounded rank-width Better algorithms for satisfiability problems for formulas of bounded rank-width Better algorithms for satisfiability problems for formulas of bounded rank-width

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 110 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software