Parameterizing above Guaranteed Values: MaxSat and MaxCut
From MaRDI portal
Publication:4242660
DOI10.1006/jagm.1998.0996zbMath0921.68052OpenAlexW2006933117MaRDI QIDQ4242660
Meena Mahajan, Venkatesh Raman
Publication date: 29 September 1999
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.1998.0996
Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)
Related Items (88)
Parameterized algorithms for feedback set problems and their duals in tournaments ⋮ A fixed-parameter algorithm for minimum quartet inconsistency ⋮ Improved exact algorithms for MAX-SAT ⋮ On Multiway Cut Parameterized above Lower Bounds ⋮ Improved Parameterized Algorithms for above Average Constraint Satisfaction ⋮ APPROXIMATE BLOCK SORTING ⋮ Simultaneous Approximation of Constraint Satisfaction Problems ⋮ Parameterizing edge modification problems above lower bounds ⋮ A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter ⋮ Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG ⋮ 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 ⋮ Parameterized complexity and approximation issues for the colorful components problems ⋮ The \(S\)-\textsc{labeling} problem: an algorithmic tour ⋮ Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments ⋮ Improved exact algorithms for mildly sparse instances of MAX SAT ⋮ An efficient fixed-parameter algorithm for 3-hitting set ⋮ Packing arc-disjoint cycles in tournaments ⋮ Computing the largest bond and the maximum connected cut of a graph ⋮ Note on maximal bisection above tight lower bound ⋮ Intractability and the use of heuristics in psychological explanations ⋮ The analysis of expected fitness and success ratio of two heuristic optimizations on two bimodal MaxSat problems ⋮ Maximum balanced subgraph problem parameterized above lower bound ⋮ Parameterized complexity of MaxSat above average ⋮ A new bound for 3-satisfiable MaxSat and its algorithmic application ⋮ Solving min ones 2-SAT as fast as vertex cover ⋮ Multidimensional Binary Vector Assignment Problem: Standard, Structural and Above Guarantee Parameterizations ⋮ Unnamed Item ⋮ On the parameterized vertex cover problem for graphs with perfect matching ⋮ Detours in directed graphs ⋮ Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables ⋮ Minimum Leaf Out-Branching Problems ⋮ Complexity of maximum cut on interval graphs ⋮ A probabilistic approach to problems parameterized above or below tight bounds ⋮ Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. ⋮ Worst-case study of local search for MAX-\(k\)-SAT. ⋮ Solving sparse instances of Max SAT via width reduction and greedy restriction ⋮ Fixed-parameter tractable algorithms for tracking shortest paths ⋮ Solving MAX-\(r\)-SAT above a tight lower bound ⋮ Betweenness parameterized above tight lower bound ⋮ Going Far from Degeneracy ⋮ The complexity of König subgraph problems and above-guarantee vertex cover ⋮ Note on Max Lin-2 above average ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound ⋮ The Complexity of Finding (Approximate Sized) Distance-d Dominating Set in Tournaments ⋮ \textsc{Max-Cut} parameterized above the Edwards-Erdős bound ⋮ Parameterized Complexity of Multi-Node Hubs ⋮ Dealing with 4-variables by resolution: an improved MaxSAT algorithm ⋮ Exact Algorithms for MAX-SAT ⋮ Fixed-parameter tractability of satisfying beyond the number of variables ⋮ Programming for modular reconfigurable robots ⋮ A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications ⋮ Unnamed Item ⋮ Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems ⋮ Unnamed Item ⋮ Linear kernels and linear-time algorithms for finding large cuts ⋮ MAX SAT approximation beyond the limits of polynomial-time approximation ⋮ Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment ⋮ Parameterized algorithmics for linear arrangement problems ⋮ Large Independent Sets in Subquartic Planar Graphs ⋮ \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel ⋮ Parameterizing above or below guaranteed values ⋮ Fixed-parameter tractable algorithm and polynomial kernel for \textsc{Max-Cut Above Spanning Tree} ⋮ Finding Detours is Fixed-Parameter Tractable ⋮ A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application ⋮ Iterative Compression for Exactly Solving NP-Hard Minimization Problems ⋮ Packing Arc-Disjoint Cycles in Tournaments ⋮ Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics ⋮ 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 ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Parameterized Complexity ⋮ A Probabilistic Approach to Problems Parameterized above or below Tight Bounds ⋮ Parameterized complexity of multi-node hubs ⋮ Revising Johnson's table for the 21st century ⋮ Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover ⋮ Parameterized complexity of finding subgraphs with hereditary properties. ⋮ A new algorithm for optimal 2-constraint satisfaction and its implications ⋮ An Empirical Study of MAX-2-SAT Phase Transitions ⋮ Improving exact algorithms for MAX-2-SAT ⋮ Parameterizations of test cover with bounded test sizes
This page was built for publication: Parameterizing above Guaranteed Values: MaxSat and MaxCut
