Name
Abstract | ||
|---|---|---|
A parallel approximation algorithm for the MAXIMUM 2-CNF SATISFIABILITYproblem is presented. This algorithm runs in O(log2(n + jF j)) parallel time on aCREW PRAM machine using O(n+jF j) processors, where n is the number of variablesand jF j is the number of clauses. Performance guarantees are considered for threeslightly differing definitions of this problem.Keywords : Satisfiability, Maximum 2-CNF SAT, Maximum Cut, Approximation Algorithm.1. IntroductionA satisfiability problem... |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1142/S0129626492000301 | Parallel Processing Letters |
Keywords | Field | DocType |
satisfiability,maximum cut,approximation algorithm | Maximum satisfiability problem,Discrete mathematics,Approximation algorithm,Combinatorics,Satisfiability,Boolean satisfiability problem,Mathematics,Maximum cut | Journal |
Volume | Citations | PageRank |
2 | 4 | 5.06 |
References | Authors | |
4 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| David J. Haglin | 1 | 112 | 19.45 |