On the parallel parameterized complexity of MaxSAT variants
type: Item
instance of: scholarly article
title: On the parallel parameterized complexity of MaxSAT variants
zbMATH Open document ID: 1543.68144
author: Max Bannach
author: Malte Skambath
author: Till Tantau
published in: The Journal of Artificial Intelligence Research (JAIR)
publication date: 2023-12-20T00:00:00Z
Mathematics Subject Classification ID: 68Q27
Mathematics Subject Classification ID: 68R07
zbMATH DE Number: 7781084
zbMATH Keywords: satisfiability
zbMATH Keywords: mathematical foundations
zbMATH Keywords: constraint satisfaction
MaRDI profile type: MaRDI publication profile
cites work: Solving MAX-\(r\)-SAT above a tight lower bound
cites work: Color-coding
cites work: On the parallel parameterized complexity of MaxSAT variants
cites work: Q5363777
cites work: Parallel Multivariate Meta-Theorems
cites work: Q5009475
cites work: On uniformity within \(NC^ 1\)
cites work: Q5148371
cites work: Advice classes of parametrized tractability
cites work: Constant Depth Reducibility
cites work: Some Lower Bounds in Parameterized AC^0.
cites work: Parameterized Parallel Computing and First-Order Logic
cites work: Slicewise Definability in First-Order Logic with Bounded Quantifier Rank.
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average
cites work: Parameterized complexity of MaxSat above average
cites work: A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications
cites work: Parameterized Algorithms
cites work: On Multiway Cut Parameterized above Lower Bounds
cites work: Complexity and approximability of parameterized MAX-CSPs
cites work: On the space and circuit complexity of parameterized problems: classes and completeness
cites work: Describing parameterized complexity classes
cites work: Maximal Flow Through a Network
cites work: Some simplified NP-complete graph problems
cites work: Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee
cites work: Guarantees and limits of preprocessing in constraint satisfaction and reasoning
cites work: The maximum flow problem is log space complete for P
cites work: The Structure of Tractable Constraint Satisfaction Problems
cites work: A new bound for 3-satisfiable MaxSat and its algorithmic application
cites work: Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
cites work: Linear-Time FPT Algorithms via Network Flow
cites work: STACS 2004
cites work: Constructing a perfect matching is in random NC
cites work: Parameterizing above Guaranteed Values: MaxSat and MaxCut
cites work: On approximation algorithms for the minimum satisfiability problem
cites work: LP can be a cure for parameterized problems
cites work: Vertex packings: Structural properties and algorithms
cites work: Sparsity. Graphs, structures, and algorithms
cites work: The Complexity of Finding Paths in Graphs with Bounded Independence Number
cites work: Optimization, approximation, and complexity classes
cites work: Parameterized circuit complexity of model-checking on sparse structures
cites work: Almost 2-SAT is fixed-parameter tractable
cites work: Finding odd cycle transversals.
cites work: The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
DOI: 10.1613/JAIR.1.14748
description: scientific article; zbMATH DE number 7781084