Parameterizing above Guaranteed Values: MaxSat and MaxCut
From MaRDI portal
Recommendations
Cited in
(98)- Parameterized algorithmics for linear arrangement problems
- Parameterizing above or below guaranteed values
- On parameterized exponential time complexity
- Almost 2-SAT is fixed-parameter tractable
- Fixed-parameter algorithms for Kemeny rankings
- Minimum leaf out-branching and related problems
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
- Worst-case study of local search for MAX-\(k\)-SAT.
- The \(S\)-\textsc{labeling} problem: an algorithmic tour
- Note on maximal bisection above tight lower bound
- Programming for modular reconfigurable robots
- \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel
- Parameterized complexity of finding subgraphs with hereditary properties.
- A fixed-parameter algorithm for minimum quartet inconsistency
- Improved exact algorithms for MAX-SAT
- The analysis of expected fitness and success ratio of two heuristic optimizations on two bimodal MaxSat problems
- Betweenness parameterized above tight lower bound
- Parameterized complexity of multi-node hubs
- Revising Johnson's table for the 21st century
- Fixed-parameter tractable algorithms for tracking shortest paths
- Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment
- Fixed-parameter tractable algorithm and polynomial kernel for \textsc{Max-Cut Above Spanning Tree}
- Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
- Improved exact algorithms for mildly sparse instances of MAX SAT
- Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Parameterizations of test cover with bounded test sizes
- Packing arc-disjoint cycles in tournaments
- Computing the largest bond and the maximum connected cut of a graph
- Large independent sets in subquartic planar graphs
- Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
- Parameterized complexity: the main ideas and connections to practical computing
- Improved parameterized algorithms for above average constraint satisfaction
- The birth and early years of parameterized complexity
- Vertex cover, dominating set and my encounters with parameterized complexity and Mike Fellows
- A basic parameterized complexity primer
- Kernelization -- preprocessing with a guarantee
- Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
- Studies in Computational Aspects of Voting
- A new bound for 3-satisfiable MaxSat and its algorithmic application
- A randomized polynomial kernelization for vertex cover with a smaller parameter
- An Empirical Study of MAX-2-SAT Phase Transitions
- Simultaneous approximation of constraint satisfaction problems
- Parameterizing MAX SNP Problems Above Guaranteed Values
- Minimum Leaf Out-Branching Problems
- Iterative Compression for Exactly Solving NP-Hard Minimization Problems
- A probabilistic approach to problems parameterized above or below tight bounds
- Intractability and the use of heuristics in psychological explanations
- Maximum balanced subgraph problem parameterized above lower bound
- A new bound for 3-satisfiable MaxSat and its algorithmic application
- Solving min ones 2-SAT as fast as vertex cover
- 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
- Exact algorithms for MAX-SAT
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- Finding detours is fixed-parameter tractable
- Parameterized constraint satisfaction problems: a survey
- Parameterized complexity of multi-node hubs
- Going far from degeneracy
- Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
- Packing Arc-Disjoint Cycles in Tournaments
- Domination above \(r\)-independence: does sparseness help?
- Going far from degeneracy
- Balanced judicious bipartition is fixed-parameter tractable
- Dealing with 4-variables by resolution: an improved MaxSAT algorithm
- Balanced Judicious Bipartition is Fixed-Parameter Tractable
- Fixed-parameter tractability of satisfying beyond the number of variables
- APPROXIMATE BLOCK SORTING
- MAX SAT approximation beyond the limits of polynomial-time approximation
- Detours in directed graphs
- Complexity of maximum cut on interval graphs
- A probabilistic approach to problems parameterized above or below tight bounds
- Solving MAX-\(r\)-SAT above a tight lower bound
- Turán’s Theorem Through Algorithmic Lens
- The complexity of König subgraph problems and above-guarantee vertex cover
- On the parallel parameterized complexity of MaxSAT variants
- Long directed detours: reduction to 2-disjoint paths
- Note on Max Lin-2 above average
- The shortest path reconfiguration problem based on relaxation of reconfiguration rules
- Changing induced subgraph isomorphisms under extended reconfiguration rules
- Complexity classes for online problems with and without predictions
- 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
- Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound
- Vertex cover and feedback vertex set above and below structural guarantees
- Changing induced subgraph isomorphisms under extended reconfiguration rules
- Cluster editing parameterized above modification-disjoint P₃-packings
- 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
- Cluster editing parameterized above modification-disjoint P₃-Packings
- Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound
- A fast algorithm for maximum satisfiability above half number of clauses
- Improving exact algorithms for MAX-2-SAT
- Parameterized algorithms for feedback set problems and their duals in tournaments
- An efficient fixed-parameter algorithm for 3-hitting set
- On the parameterized vertex cover problem for graphs with perfect matching
- Solving sparse instances of Max SAT via width reduction and greedy restriction
This page was built for publication: Parameterizing above Guaranteed Values: MaxSat and MaxCut
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4242660)
