A linear-time algorithm for testing the truth of certain quantified Boolean formulas

Cites work

Depth-First Search and Linear Graph Algorithms
scientific article; zbMATH DE number 3511563 (Why is no real title available?)
scientific article; zbMATH DE number 3560737 (Why is no real title available?)
scientific article; zbMATH DE number 3573250 (Why is no real title available?)
On the Complexity of Timetable and Multicommodity Flow Problems
The complexity of satisfiability problems
The complexity of theorem-proving procedures

Cited in

(only showing first 100 items - show all)

The complexity of satisfiability problems: Refining Schaefer's theorem
Red-blue covering problems and the consecutive ones property
Probe threshold and probe trivially perfect graphs
On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls
Backdoor sets of quantified Boolean formulas
Uniquely solvable quadratic Boolean equations
An extension of the König-Egerváry property to node-weighted bidirected graphs
Optimizing propositional calculus formulas with regard to questions of deducibility
A fast algorithm for solving systems of linear equations with two variables per equation
A switching algorithm for the solution of quadratic Boolean equations
An analytical approach to global optimization
Capturing complexity classes by fragments of second-order logic
An efficient algorithm for the 3-satisfiability problem
Optimal cell flipping to minimize channel density in VLSI design and pseudo-Boolean optimization
Simulated annealing for the unconstrained quadratic pseudo-Boolean function
Recognition of q-Horn formulae in linear time
Minimization of a quadratic pseudo-Boolean function
The unique Horn-satisfiability problem and quadratic Boolean equations.
Polynomial-time inference of all valid implications for Horn and related formulae
On renamable Horn and generalized Horn functions
On-line 2-satisfiability
Positive and Horn decomposability of partially defined Boolean functions
An algorithm reconstructing convex lattice sets.
Non-Horn clause logic programming
The maximum length of prime implicates for instances of 3-SAT
Semantics and complexity of abduction from default theories
Reconstruction of convex 2D discrete sets in polynomial time
Logical analysis of binary data with missing bits
On functional dependencies in q-Horn theories
Reconstructing \(hv\)-convex polyominoes from orthogonal projections
Random 2-SAT and unsatisfiability
Disjunctions, independence, refinements
New results on edge partitions of 1-plane graphs
Recognition of unipolar and generalised split graphs
Co-clustering under the maximum norm
A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
The P versus NP-complete dichotomy of some challenging problems in graph theory
Correlations between Horn fractions, satisfiability and solver performance for fixed density random 3-CNF instances
On exact selection of minimally unsatisfiable subformulae
Solving the resolution-free SAT problem by submodel propagation in linear time
Toward leaner binary-clause reasoning in a satisfiability solver
A polynomial-time algorithm to find an equitable home--away assignment
Three-coloring and list three-coloring of graphs without induced paths on seven vertices
Selecting and covering colored points
Constraint-generating dependencies
On the r,s-SAT satisfiability problem and a conjecture of Tovey
On subclasses of minimal unsatisfiable formulas
Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT
Recognition and dualization of disguised bidual Horn functions.
A short note on some tractable cases of the satisfiability problem.
Detection of the discrete convexity of polyominoes
A perspective on certain polynomial-time solvable classes of satisfiability
The number of 2-SAT functions
Local base station assignment with time intervals in mobile computing environments
2-satisfiability and diagnosing fault processors in massively parallel computing systems
A new algorithm for the propositional satisfiability problem
Decomposability of partially defined Boolean functions
3-colouring AT-free graphs in polynomial time
A tighter upper bound for random MAX \(2\)-SAT
On the exact complexity of evaluating quantified \(k\)-\textsc{cnf}
Maximum renamable Horn sub-CNFs
Satisfiability threshold for random XOR-CNF formulas
The Multi-SAT algorithm
A remark on random 2-SAT
Two tractable subclasses of minimal unsatisfiable formulas
Recognition of tractable satisfiability problems through balanced polynomial representations
On k-positive satisfiability problem
Consistent query answering for primary keys in Datalog
New and improved algorithms for unordered tree inclusion
An improved algorithm for the (n, 3)-MaxSAT problem: asking branchings to satisfy the clauses
Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas
Worst-case analysis of clique MIPs
Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
Space efficient merging of de Bruijn graphs and Wheeler graphs
Probabilistic state estimation for labeled continuous time Markov models with applications to attack detection
Planar straight-line realizations of 2-trees with prescribed edge lengths
Makespan minimization on unrelated parallel machines with a few bags
On the complexity of cd-coloring of graphs
A recognition algorithm for simple-triangle graphs
Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
The complete set of minimal simple graphs that support unsatisfiable 2-CNFs
Two polynomial time graph labeling algorithms optimizing max-norm-based objective functions
Facets from gadgets
Labeling nonograms: boundary labeling for curve arrangements
Optimization for first order Delaunay triangulations
Unconstrained 0-1 optimization and Lagrangean relaxation
Faster graph bipartization
Stable matching with uncertain linear preferences
Solving and sampling with many solutions
Compact linear programs for 2SAT
Detecting strong cliques
New complexity results for Łukasiewicz logic
Minimal distance of propositional models
The Horn renamability, q-Horn and SLUR threshold for random \(k\)-CNF formulas
The complexity of string partitioning
Disconnectivity and relative positions in simultaneous embeddings
An efficiently solvable graph partition problem to which many problems are reducible
Known and new classes of generalized Horn formulae with polynomial recognition and SAT testing
Domain permutation reduction for constraint satisfaction problems
What makes propositional abduction tractable

This page was built for publication: A linear-time algorithm for testing the truth of certain quantified Boolean formulas

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