A SAT approach to twin-width

DOI10.1137/1.9781611977042.6MaRDI QIDQ6543128zbMATH OpenFDO

Authors André Schidler, Stefan Szeider

Publication date 24 May 2024

Full work available at URL https://doi.org/10.1137/1.9781611977042.6

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Twin-width. I: Tractable FO model checking
• Twin-width. III: Max independent set, min dominating set, and coloring

Cited in

(14)

• Twin-width of random graphs
• Twin-width of graphs with tree-structured decompositions
• Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
• Computing and certifying twin-width using logic
• On the twin-width of near-regular graphs
• Faster graph algorithms through DAG compression
• On the twin-width of outerplanar graphs
• Randomized communication and implicit graph representations
• PACE solver description: Touiouidth
• PACE solver description: exact (GUTHMI) and heuristic (GUTHM)
• PACE solver description: hydra prime
• PACE solver description: the PACE 2023 parameterized algorithms and computational experiments challenge: twinwidth
• 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: A SAT approach to twin-width

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