Twin-width. I: Tractable FO model checking
From MaRDI portal
Publication:5066940
DOI10.1145/3486655OpenAlexW3216575656WikidataQ131564831 ScholiaQ131564831MaRDI QIDQ5066940FDOQ5066940
Authors: Édouard Bonnet, Eun Jung Kim, Rémi Watrigant, Stéphan Thomassé 
Publication date: 31 March 2022
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2004.14789
Recommendations
Cited In (44)
- On the thinness of trees
- Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
- Functionality of box intersection graphs
- Treewidth versus clique number. II: Tree-independence number
- Parity permutation pattern matching
- Graphs of bounded twin-width are quasi-polynomially \(\chi \)-bounded
- Twin-width can be exponential in treewidth
- Twin-width and transductions of proper \(k\)-mixed-thin graphs
- Hypergraphs with polynomial representation: introducing \(r\)-splits
- Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
- Twin-width. II: Small classes
- Grouped domination parameterized by vertex cover, twin cover, and beyond
- Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
- Parity permutation pattern matching
- On \(( n , m )\)-chromatic numbers of graphs with bounded sparsity parameters
- Transducing paths in graph classes with unbounded shrubdepth
- Planar graph with twin-width seven
- Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
- Mini-workshop: Permutation patterns. Abstracts from the mini-workshop held January 28 -- February 2, 2024
- Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
- Stack-number is not bounded by queue-number
- Counting subgraphs in somewhere dense graphs
- \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs
- Neighbourhood complexity of graphs of bounded twin-width
- Twin-width. III: Max independent set, min dominating set, and coloring
- Twin-width of random graphs
- Stable graphs of bounded twin-width
- The splitting power of branching programs of bounded repetition and CNFs of bounded width
- Treelike decompositions for transductions of sparse graphs
- Model checking on interpretations of classes of bounded local cliquewidth
- A meta-theorem for distributed certification
- Bounds for the twin-width of graphs
- Complexity of maker-breaker games on edge sets of graphs
- Vertex-minors of graphs: a survey
- Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
- Twin-width of graphs with tree-structured decompositions
- Graph product structure for \(h\)-framed graphs
- Twin-width and transductions of proper \(k\)-mixed-thin graphs
- A SAT approach to twin-width
- Twin-width and polynomial kernels
- A meta-theorem for distributed certification
- Tree-width for first order formulae
- Grouped domination parameterized by vertex cover, twin cover, and beyond
- Bounds on the Twin-Width of Product Graphs
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 Q5066940)
