Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey (Q2908541)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey	scientific article

Statements

scholarly article

0 references

Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey (English)

0 references

0 references

0 references

The Multivariate Algorithmic Revolution and Beyond

0 references

publication date

5 September 2012

0 references

full work available at URL

https://arxiv.org/abs/1108.4803

0 references

describes a project that uses

0 references

MaRDI profile type

MaRDI publication profile

0 references

Voting paradoxes and digraphs realizations

0 references

Solving MAX-\(r\)-SAT above a tight lower bound

0 references

Algorithms with large domination ratio

0 references

0 references

On problems without polynomial kernels

0 references

Kernel bounds for disjoint cycles and disjoint paths

0 references

Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)

0 references

Vertex Cover: Further Observations and Further Improvements

0 references

Crown reductions for the minimum weighted vertex cover problem

0 references

A Geometric Approach to Betweenness

0 references

Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average

0 references

Note on Max Lin-2 above average

0 references

Systems of Linear Equations over $\mathbb{F}_2$ and Problems Parameterized above Average

0 references

Parameterized complexity of MaxSat above average

0 references

A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications

0 references

On the Hardness of Losing Width

0 references

Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves

0 references

Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.

0 references

Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant

0 references

Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables

0 references

A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application

0 references

Betweenness parameterized above tight lower bound

0 references

A probabilistic approach to problems parameterized above or below tight bounds

0 references

Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width

0 references

Some optimal inapproximability results

0 references

On the advantage over a random assignment

0 references

A new approach to cyclic ordering of 2D orientations using ternary relation algebras

0 references

0 references

0 references

On the power of unique 2-prover 1-round games

0 references

Improved Parameterized Algorithms for above Average Constraint Satisfaction

0 references

A kernel of order \(2k-c\log k\) for vertex cover

0 references

Complexity of Partial Satisfaction

0 references

Complexity of partial satisfaction. II.

0 references

Parameterizing above Guaranteed Values: MaxSat and MaxCut

0 references

Parameterizing MAX SNP Problems Above Guaranteed Values

0 references

The complexity of König subgraph problems and above-guarantee vertex cover

0 references

Vertex packings: Structural properties and algorithms

0 references

0 references

Total Ordering Problem

0 references

Paths, Flowers and Vertex Cover

0 references

Almost 2-SAT is fixed-parameter tractable

0 references

0 references

A kernel of order \(2k - c\) for Vertex Cover

0 references

Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable

0 references

On the Approximation of Maximum Satisfiability

0 references

Identifiers

zbMATH Open document ID

0 references

10.1007/978-3-642-30891-8_14

0 references

Mathematics Subject Classification ID

0 references

zbMATH DE Number

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2908541

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q2908541&oldid=35297027"