Parameterizing above or below guaranteed values
From MaRDI portal
above guarantee parameterizationsfixed-parameter tractabilityNP-optimization problemsparameterized complexity
Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Recommendations
Cites work
- .878-approximation algorithms for MAX CUT and MAX 2SAT
- A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
- Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
- Approximating minimum feedback sets and multicuts in directed graphs
- Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
- Approximation algorithms for NP-complete problems on planar graphs
- Chordal Deletion Is Fixed-Parameter Tractable
- Faster fixed parameter tractable algorithms for finding feedback vertex sets
- Finding odd cycle transversals.
- Fixed-Parameter Algorithms for Kemeny Scores
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- Fixed-Parameter Complexity of Minimum Profile Problems
- scientific article; zbMATH DE number 5485472 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- scientific article; zbMATH DE number 1420899 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Independence numbers of graphs - an extension of the Koenig-Egervary theorem
- New Upper Bounds for Maximum Satisfiability
- Obtaining a Planar Graph by Vertex Deletion
- On fixed-parameter tractability and approximability of NP optimization problems
- On interval graphs and matrice profiles
- On Parameterized Approximability
- On Syntactic versus Computational Views of Approximability
- On the advantage over a random assignment
- Optimization, approximation, and complexity classes
- Parameterized Approximation Problems
- Parameterized complexity of finding subgraphs with hereditary properties.
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Parameterizing MAX SNP Problems Above Guaranteed Values
- Parametrized complexity theory.
- Profile minimization problem for matrices and graphs
- Recognizing Berge graphs
- The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
- The Linear Arrangement Problem Parameterized Above Guaranteed Value
- Wheel-Free Deletion Is W[2]-Hard
Cited in
(51)- Note on maximal bisection above tight lower bound
- Betweenness parameterized above tight lower bound
- Greed is good for deterministic scale-free networks
- Fixed-parameter tractable algorithms for tracking shortest paths
- Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
- Parameterizations of test cover with bounded test sizes
- On the kernelization of split graph problems
- Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
- Large independent sets in subquartic planar graphs
- Improved parameterized algorithms for above average constraint satisfaction
- The Impact of Parameterized Complexity to Interdisciplinary Problem Solving
- Studies in Computational Aspects of Voting
- Ranking and drawing in subexponential time
- Partial kernelization for rank aggregation: theory and experiments
- A new bound for 3-satisfiable MaxSat and its algorithmic application
- Acyclic digraphs
- Simultaneous approximation of constraint satisfaction problems
- A probabilistic approach to problems parameterized above or below tight bounds
- Maximum balanced subgraph problem parameterized above lower bound
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- The complexity of finding (approximate sized) distance-d dominating set in tournaments
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- Finding detours is fixed-parameter tractable
- Parameterized constraint satisfaction problems: a survey
- Going far from degeneracy
- Domination above \(r\)-independence: does sparseness help?
- Going far from degeneracy
- Balanced judicious bipartition is fixed-parameter tractable
- Balanced Judicious Bipartition is Fixed-Parameter Tractable
- Large independent sets in triangle-free planar graphs
- Fixed-parameter tractability of satisfying beyond the number of variables
- Parameterized traveling salesman problem: beating the average
- Multiplicative Parameterization Above a Guarantee
- Recognizing \(k\)-clique extendible orderings
- Detours in directed graphs
- A probabilistic approach to problems parameterized above or below tight bounds
- Vertex cover problem parameterized above and below tight bounds
- Solving MAX-\(r\)-SAT above a tight lower bound
- Turán’s Theorem Through Algorithmic Lens
- Note on Max Lin-2 above average
- The shortest path reconfiguration problem based on relaxation of reconfiguration rules
- Approximating long cycle above Dirac's guarantee
- A faster algorithm for vertex cover parameterized by solution size
- On the complexity of finding a sparse connected spanning subgraph in a non-uniform failure model
- Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width
- Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
- Linear kernels and linear-time algorithms for finding large cuts
- A fast algorithm for maximum satisfiability above half number of clauses
- On the parameterized vertex cover problem for graphs with perfect matching
This page was built for publication: Parameterizing above or below guaranteed values
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1004602)
