A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem

DOI10.4153/CJM-1982-036-8zbMath0471.68041OpenAlexW2312821511WikidataQ94994198 ScholiaQ94994198MaRDI QIDQ3926050

Publication date: 1982

Published in: Canadian Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4153/cjm-1982-036-8

zbMATH Keywords

Boolean expressions in conjunctive form

Mathematics Subject Classification ID

Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).

Related Items (13)

Parameterized algorithms for feedback set problems and their duals in tournaments ⋮ Approximation of Constraint Satisfaction via local search ⋮ Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG ⋮ Linear-Time Approximation Algorithms for the Max Cut Problem ⋮ Maximum bipartite subgraphs of Kneser graphs ⋮ \textsc{Max-Cut} parameterized above the Edwards-Erdős bound ⋮ On existence theorems ⋮ Max-cut in circulant graphs ⋮ The cut cone. III: On the role of triangle facets ⋮ The cut cone. III: On the role of triangle facets ⋮ Parameterizing above or below guaranteed values ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound

This page was built for publication: A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem