Linear-Time Approximation Algorithms for the Max Cut Problem

DOI10.1017/S0963548300000596zbMath0803.68086MaRDI QIDQ4290088

Nguyen Van Ngoc, Zsolt Tuza

Publication date: 28 April 1994

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

zbMATH Keywords

connected graphbipartite subgraphmax cut\(k\)-colourable subgraph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)

Related Items

The expected relative error of the polyhedral approximation of the max- cut problem ⋮ A construction method for optimally universal hash families and its consequences for the existence of RBIBDs ⋮ Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs ⋮ \textsc{Max-Cut} parameterized above the Edwards-Erdős bound ⋮ Linear kernels and linear-time algorithms for finding large cuts ⋮ Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3 ⋮ Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality

Cites Work

• Unnamed Item
• How to make a graph bipartite
• Graph coloring in linear time
• A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
• Graph Theory and Probability
• A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
• Improved lower bounds on k‐independence
• A note on bipartite subgraphs of triangle‐free graphs
• Some Extremal Properties of Bipartite Subgraphs