Weighted model counting with twin-width

DOI10.4230/LIPICS.SAT.2022.15MaRDI QIDQ6572028zbMATH OpenFDO

Authors Robert Ganian, Filip Pokrývka, André Schidler, Kirill Simonov, Stefan Szeider

Publication date 12 July 2024

Full work available at URL https://doi.org/10.4230/LIPICS.SAT.2022.15

zbMATH Keywords

parameterized complexitySATtwin-widthweighted model counting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects of satisfiability (68R07) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cited in

(8)

• Twin-width of random graphs
• Isomorphism for tournaments of small twin width
• Computing and certifying twin-width using logic
• Faster graph algorithms through DAG compression
• Computing twin-width parameterized by the feedback edge number
• Computing twin-width parameterized by the feedback edge number and vertex integrity
• Twin-width of subdivisions of multigraphs
• Improved bounds for twin-width parameter variants with algorithmic applications to counting graph colorings

This page was built for publication: Weighted model counting with twin-width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6572028)