Linear-Time Approximation Algorithms for the Max Cut Problem
From MaRDI portal
Recommendations
Cites work
- A note on bipartite subgraphs of triangle‐free graphs
- A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
- A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
- Graph coloring in linear time
- Graph Theory and Probability
- How to make a graph bipartite
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Improved lower bounds on k‐independence
- Some Extremal Properties of Bipartite Subgraphs
Cited in
(26)- 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
- Expected complexity of graph partitioning problems
- Linear-time recognition of bipartite graphs plus two edges
- The expected relative error of the polyhedral approximation of the max- cut problem
- Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results
- Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
- A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem
- An exact algorithm for MAX-CUT in sparse graphs
- Approximate Max k-Cut with subgraph guarantee
- Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time
- scientific article; zbMATH DE number 4135976 (Why is no real title available?)
- scientific article; zbMATH DE number 1787231 (Why is no real title available?)
- Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts
- A combinatorial design approach to MAXCUT
- scientific article; zbMATH DE number 6850401 (Why is no real title available?)
- On the number of maximal bipartite subgraphs of a graph
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- Streaming Lower Bounds for Approximating MAX-CUT
- scientific article; zbMATH DE number 5232308 (Why is no real title available?)
- scientific article; zbMATH DE number 5237271 (Why is no real title available?)
- scientific article; zbMATH DE number 7650221 (Why is no real title available?)
- Linear kernels and linear-time algorithms for finding large cuts
- A linear time algorithm for the maximum capacity path problem
- A construction method for optimally universal hash families and its consequences for the existence of RBIBDs
- Finding bipartite subgraphs efficiently
This page was built for publication: Linear-Time Approximation Algorithms for the Max Cut Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4290088)
