Publication:4242660

DOI10.1006/JAGM.1998.0996zbMATH Open0921.68052OpenAlexW2006933117MaRDI QIDQ4242660FDOQ4242660

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

zbMATH Keywords

MaxCutMaxSat

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Cited In (93)

• 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
• Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
• 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
• Exact Algorithms for MAX-SAT
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• Computing the largest bond and the maximum connected cut of a graph
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• MAX SAT approximation beyond the limits of polynomial-time approximation
• An efficient fixed-parameter algorithm for 3-hitting set
• Complexity of maximum cut on interval graphs
• Minimum Leaf Out-Branching Problems
• Minimum leaf out-branching and related problems
• Solving MAX-\(r\)-SAT above a tight lower bound
• Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
• Parameterizing edge modification problems above lower bounds
• Parameterizing above or below guaranteed values
• Worst-case study of local search for MAX-\(k\)-SAT.
• Almost 2-SAT is fixed-parameter tractable
• APPROXIMATE BLOCK SORTING
• Improving exact algorithms for MAX-2-SAT
• Note on maximal bisection above tight lower bound
• Packing Arc-Disjoint Cycles in Tournaments
• Linear kernels and linear-time algorithms for finding large cuts
• Kernelization – Preprocessing with a Guarantee
• Parameterized complexity of finding subgraphs with hereditary properties.
• The complexity of König subgraph problems and above-guarantee vertex cover
• On the parameterized vertex cover problem for graphs with perfect matching
• A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• Detours in directed graphs
• A fixed-parameter algorithm for minimum quartet inconsistency
• Betweenness parameterized above tight lower bound
• The \(S\)-\textsc{labeling} problem: an algorithmic tour
• A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
• Parameterized complexity: the main ideas and connections to practical computing
• A Basic Parameterized Complexity Primer
• Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
• Fixed-parameter algorithms for Kemeny rankings
• Improved Parameterized Algorithms for above Average Constraint Satisfaction
• On parameterized exponential time complexity
• Parameterized algorithmics for linear arrangement problems
• A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application
• Parameterized algorithms for feedback set problems and their duals in tournaments
• Solving sparse instances of Max SAT via width reduction and greedy restriction
• Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment
• On Multiway Cut Parameterized above Lower Bounds
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Parameterizing MAX SNP Problems Above Guaranteed Values
• An Empirical Study of MAX-2-SAT Phase Transitions
• Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
• Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
• Programming for modular reconfigurable robots
• Parameterized complexity and approximation issues for the colorful components problems
• A Probabilistic Approach to Problems Parameterized above or below Tight Bounds
• Packing arc-disjoint cycles in tournaments
• Intractability and the use of heuristics in psychological explanations
• Improved exact algorithms for MAX-SAT
• Dealing with 4-variables by resolution: an improved MaxSAT algorithm
• \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
• Improved exact algorithms for mildly sparse instances of MAX SAT
• Fixed-parameter tractability of satisfying beyond the number of variables
• Long directed detours: reduction to 2-disjoint paths
• Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
• Title not available (Why is that?)
• The shortest path reconfiguration problem based on relaxation of reconfiguration rules
• Balanced Judicious Bipartition is Fixed-Parameter Tractable
• Vertex Cover, Dominating Set and My Encounters with Parameterized Complexity and Mike Fellows
• Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
• Simultaneous Approximation of Constraint Satisfaction Problems
• The Complexity of Finding (Approximate Sized) Distance-d Dominating Set in Tournaments
• Finding Detours is Fixed-Parameter Tractable
• Going Far from Degeneracy
• Title not available (Why is that?)
• On the parallel parameterized complexity of MaxSAT variants
• The Birth and Early Years of Parameterized Complexity
• The analysis of expected fitness and success ratio of two heuristic optimizations on two bimodal MaxSat problems
• Title not available (Why is that?)
• Balanced Judicious Bipartition is Fixed-Parameter Tractable
• \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel
• Multidimensional Binary Vector Assignment Problem: Standard, Structural and Above Guarantee Parameterizations
• Large Independent Sets in Subquartic Planar Graphs
• Turán’s Theorem Through Algorithmic Lens
• Fixed-parameter tractable algorithm and polynomial kernel for \textsc{Max-Cut Above Spanning Tree}
• Parameterized complexity of multi-node hubs
• Fixed-parameter tractable algorithms for tracking shortest paths
• Parameterized Complexity of Multi-Node Hubs
• Revising Johnson's table for the 21st century

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)