Exact enumeration of satisfiable 2-SAT formulae

DOI10.5070/c63261985arXiv2108.08067OpenAlexW3194217435MaRDI QIDQ6138912

Elie de Panafieu, Vlady Ravelomanana, Sergey Dovgal

Publication date: 16 December 2023

Published in: Combinatorial Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2108.08067

zbMATH Keywords

generating functionsphase transitionsrandom graphssatisfiabilityexact enumerationstrongly connected components2-CNF

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Random 2 XORSAT phase transition
• A threshold for unsatisfiability
• The asymptotic \(k\)-SAT threshold
• How frequently is a system of 2-linear Boolean equations solvable?
• Une théorie combinatoire des séries formelles
• Some simplified NP-complete graph problems
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Airy phenomena and analytic combinatorics of connected graphs
• Enumerative applications of a decomposition for graphs and digraphs
• Phase transition of random non-uniform hypergraphs
• Proof of the satisfiability conjecture for large \(k\)
• Threshold functions for small subgraphs in simple graphs and multigraphs
• Counting directed acyclic and elementary digraphs
• The continuum limit of critical random graphs
• The scaling window of the 2-SAT transition
• The critical behavior of random digraphs
• The transitive closure of a random digraph
• The phase transition in the evolution of random digraphs
• On Some Features of the Structure of a Random Graph Near a Critical Point
• An Asymptotic Expansion for the Coefficients of Some Formal Power Series
• The number of connected sparsely edged graphs
• Random MAX SAT, random MAX CUT, and their phase transitions
• Paths in graphs
• Analytic combinatorics of connected graphs
• The birth of the giant component
• Some optimal inapproximability results
• The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
• The Number of Strong Digraphs
• The complexity of theorem-proving procedures
• Random 2-SAT: Results and problems

This page was built for publication: Exact enumeration of satisfiable 2-SAT formulae