On using SAT solvers for graph computations

DOI10.1016/J.DAM.2025.10.017MaRDI QIDQ6883369zbMATH OpenFDO

Authors Bruno Courcelle, Irène Durand

Publication date 16 December 2025

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.10.017

zbMATH Keywords

clique-widthexcluded subgraphSAT problemtournament

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Computational aspects of satisfiability (68R07) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A SAT approach to clique-width
• Approximating rank-width and clique-width quickly
• Automata for the verification of monadic second-order graph properties
• Betweenness in order-theoretic trees
• Classes of directed graphs
• Clique-width and edge contraction
• Clique-width is NP-complete
• Elements of finite model theory.
• Encoding Treewidth into SAT
• Graph structure and monadic second-order logic. A language-theoretic approach
• scientific article; zbMATH DE number 2044940 (Why is no real title available?)
• scientific article; zbMATH DE number 3400958 (Why is no real title available?)
• Linear rank-width and linear clique-width of trees
• On quasi-planar graphs: clique-width and logical description
• On the clique-width of some perfect graph classes
• The behavior of clique-width under graph operations and graph transformations
• The monadic second-order logic of graphs. VIII: Orientations
• The relative clique-width of a graph
• Theory of relations. Transl. from the French by P. Clote. With an appendix by Norbert Sauer.
• Well-quasi-order of relabel functions

This page was built for publication: On using SAT solvers for graph computations

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