Parameterizing above Guaranteed Values: MaxSat and MaxCut
- 31 May 1999
- journal article
- Published by Elsevier BV in Journal of Algorithms
- Vol. 31 (2), 335-354
- https://doi.org/10.1006/jagm.1998.0996
Abstract
No abstract availableKeywords
This publication has 20 references indexed in Scilit:
- An improved fixed-parameter algorithm for vertex coverInformation Processing Letters, 1998
- On Fixed-Parameter Tractability and Approximability of NP Optimization ProblemsJournal of Computer and System Sciences, 1997
- On the Amount of Nondeterminism and the Power of VerifyingSIAM Journal on Computing, 1997
- A linear-time algorithm for computing the intersection of all odd cycles in a graphDiscrete Applied Mathematics, 1997
- On input read-modes of alternating Turing machinesTheoretical Computer Science, 1995
- Fixed-Parameter Tractability and Completeness I: Basic ResultsSIAM Journal on Computing, 1995
- Fixed-parameter tractability and completeness II: On completeness for W[1]Theoretical Computer Science, 1995
- The Minimum Satisfiability ProblemSIAM Journal on Discrete Mathematics, 1994
- Approximation and intractability results for the maximum cut problem and its variantsIEEE Transactions on Computers, 1991
- Some Extremal Properties of Bipartite SubgraphsCanadian Journal of Mathematics, 1973