scientific article; zbMATH DE number 7359812
From MaRDI portal
Publication:4993600
DOI10.4230/DFU.Vol7.15301.179zbMath1482.68111MaRDI QIDQ4993600
Publication date: 15 June 2021
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Combinatorics in computer science (68R05) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Parameterized complexity of MaxSat above average
- A new bound for 3-satisfiable MaxSat and its algorithmic application
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- A probabilistic approach to problems parameterized above or below tight bounds
- Kernel bounds for disjoint cycles and disjoint paths
- Solving MAX-\(r\)-SAT above a tight lower bound
- Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width
- Parameterizing above or below guaranteed values
- On problems without polynomial kernels
- Almost 2-SAT is fixed-parameter tractable
- On fixed-parameter tractability and approximability of NP optimization problems
- A new approach to cyclic ordering of 2D orientations using ternary relation algebras
- Note on maximal bisection above tight lower bound
- A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications
- Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
- Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
- Voting paradoxes and digraphs realizations
- Betweenness parameterized above tight lower bound
- Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
- Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
- On Multiway Cut Parameterized above Lower Bounds
- Improved Parameterized Algorithms for above Average Constraint Satisfaction
- Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
- Paths, Flowers and Vertex Cover
- Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant
- Systems of Linear Equations over $\mathbb{F}_2$ and Problems Parameterized above Average
- On the power of unique 2-prover 1-round games
- Complexity of Partial Satisfaction
- Total Ordering Problem
- A Geometric Approach to Betweenness
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- On the Approximation of Maximum Satisfiability
- Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints
- Algorithms with large domination ratio
- Analysis of Boolean Functions
- Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
- Some optimal inapproximability results
- Parameterized Algorithms
This page was built for publication: