Parameterizing above or below guaranteed values
From MaRDI portal
Publication:1004602
DOI10.1016/J.JCSS.2008.08.004zbMATH Open1155.68400OpenAlexW2008444606MaRDI QIDQ1004602FDOQ1004602
Authors: Meena Mahajan, Venkatesh Raman, Somnath Sikdar 
Publication date: 11 March 2009
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2008.08.004
Recommendations
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)
Cites Work
- Optimization, approximation, and complexity classes
- Finding odd cycle transversals.
- Independence numbers of graphs - an extension of the Koenig-Egervary theorem
- Parametrized complexity theory.
- Faster fixed parameter tractable algorithms for finding feedback vertex sets
- Parameterized Approximation Problems
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Approximation algorithms for NP-complete problems on planar graphs
- Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
- Title not available (Why is that?)
- Recognizing Berge graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- .878-approximation algorithms for MAX CUT and MAX 2SAT
- Approximating minimum feedback sets and multicuts in directed graphs
- Title not available (Why is that?)
- On Syntactic versus Computational Views of Approximability
- Parameterized complexity of finding subgraphs with hereditary properties.
- Parameterizing MAX SNP Problems Above Guaranteed Values
- On Parameterized Approximability
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- New Upper Bounds for Maximum Satisfiability
- A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
- Obtaining a Planar Graph by Vertex Deletion
- Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
- The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
- On fixed-parameter tractability and approximability of NP optimization problems
- Profile minimization problem for matrices and graphs
- Chordal Deletion Is Fixed-Parameter Tractable
- On interval graphs and matrice profiles
- Wheel-Free Deletion Is W[2]-Hard
- The Linear Arrangement Problem Parameterized Above Guaranteed Value
- Fixed-Parameter Complexity of Minimum Profile Problems
- Fixed-Parameter Algorithms for Kemeny Scores
- Title not available (Why is that?)
- On the advantage over a random assignment
Cited In (48)
- Balanced judicious bipartition is fixed-parameter tractable
- A new bound for 3-satisfiable MaxSat and its algorithmic application
- 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
- Ranking and drawing in subexponential time
- Studies in Computational Aspects of Voting
- A probabilistic approach to problems parameterized above or below tight bounds
- Parameterizations of test cover with bounded test sizes
- Note on Max Lin-2 above average
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- The shortest path reconfiguration problem based on relaxation of reconfiguration rules
- Solving MAX-\(r\)-SAT above a tight lower bound
- 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
- Multiplicative Parameterization Above a Guarantee
- Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width
- Approximating long cycle above Dirac's guarantee
- Note on maximal bisection above tight lower bound
- Parameterized traveling salesman problem: beating the average
- Title not available (Why is that?)
- Improved parameterized algorithms for above average constraint satisfaction
- Linear kernels and linear-time algorithms for finding large cuts
- 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
- Parameterized constraint satisfaction problems: a survey
- \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
- 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)
