Parameterizing above or below guaranteed values
From MaRDI portal
fixed-parameter tractabilityparameterized complexityNP-optimization problemsabove guarantee parameterizations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of computation (including implicit computational complexity) (03D15)
Recommendations
Cites work
- 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?)
- .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-Size k-Connected Spanning Subgraphs via Matching
- Approximating minimum feedback sets and multicuts in directed graphs
- 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
- 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 Parameterized Approximability
- On Syntactic versus Computational Views of Approximability
- On fixed-parameter tractability and approximability of NP optimization problems
- On interval graphs and matrice profiles
- On the advantage over a random assignment
- Optimization, approximation, and complexity classes
- Parameterized Approximation Problems
- Parameterized complexity of finding subgraphs with hereditary properties.
- Parameterizing MAX SNP Problems Above Guaranteed Values
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- 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
(48)- 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
- A new bound for 3-satisfiable MaxSat and its algorithmic application
- Balanced judicious bipartition is fixed-parameter tractable
- Ranking and drawing in subexponential time
- Studies in Computational Aspects of Voting
- Parameterizations of test cover with bounded test sizes
- A probabilistic approach to problems parameterized above or below tight bounds
- Note on Max Lin-2 above average
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- Solving MAX-\(r\)-SAT above a tight lower bound
- The shortest path reconfiguration problem based on relaxation of reconfiguration rules
- Balanced Judicious Bipartition is Fixed-Parameter Tractable
- The Impact of Parameterized Complexity to Interdisciplinary Problem Solving
- A probabilistic approach to problems parameterized above or below tight bounds
- Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width
- Multiplicative Parameterization Above a Guarantee
- Note on maximal bisection above tight lower bound
- Approximating long cycle above Dirac's guarantee
- Parameterized traveling salesman problem: beating the average
- Linear kernels and linear-time algorithms for finding large cuts
- Improved parameterized algorithms for above average constraint satisfaction
- scientific article; zbMATH DE number 7525484 (Why is no real title available?)
- On the parameterized vertex cover problem for graphs with perfect matching
- Partial kernelization for rank aggregation: theory and experiments
- Detours in directed graphs
- Betweenness parameterized above tight lower bound
- On the kernelization of split graph problems
- Acyclic digraphs
- Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
- Large independent sets in subquartic planar graphs
- Domination above \(r\)-independence: does sparseness help?
- Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
- Recognizing \(k\)-clique extendible orderings
- Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
- Going far from degeneracy
- Finding detours is fixed-parameter tractable
- Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
- The complexity of finding (approximate sized) distance-\(d\) dominating set in tournaments
- Turán’s Theorem Through Algorithmic Lens
- Large independent sets in triangle-free planar graphs
- Simultaneous approximation of constraint satisfaction problems
- Vertex cover problem parameterized above and below tight bounds
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- Fixed-parameter tractable algorithms for tracking shortest paths
- Greed is good for deterministic scale-free networks
- Parameterized constraint satisfaction problems: a survey
- Fixed-parameter tractability of satisfying beyond the number of variables
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)
