Twin-width. I: Tractable FO model checking

DOI10.1109/FOCS46700.2020.00062MaRDI QIDQ6943994zbMATH OpenFDO

Authors Stéphan Thomassé, Rémi Watrigant, Édouard Bonnet, Eun Jung Kim

Publication date 12 August 2025

Full work available at URL https://doi.org/10.1109/FOCS46700.2020.00062

Mathematics Subject Classification ID

Proceedings, conferences, collections, etc. pertaining to computer science (68-06)

Cited in

(15)

• Faster graph algorithms through DAG compression
• Twin-width of planar graphs is at most 8, and some related bounds
• PACE solver description: hydra prime
• PACE solver description: the PACE 2023 parameterized algorithms and computational experiments challenge: twinwidth
• Twin-width of graphs with tree-structured decompositions
• Sparse graphs of twin-width 2 have bounded tree-width
• On first-order transductions of classes of graphs
• Elementary first-order model checking for sparse graphs
• Twin-width and permutations (extended abstract)
• Shallow vertex minors, stability, and dependence
• Twin-width. IV: Ordered graphs and matrices
• Improved bounds for twin-width parameter variants with algorithmic applications to counting graph colorings
• Twin-width of graphs on surfaces
• Twin-width. III: Max independent set, min dominating set, and coloring
• Solving partial dominating set and related problems using twin-width

This page was built for publication: Twin-width. I: Tractable FO model checking

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