Approximation and intractability results for the maximum cut problem and its variants

DOI10.1109/12.67327zbMath1395.68139OpenAlexW2097277086MaRDI QIDQ5375386

Shankar M. Venkatesan, David J. Haglin

Publication date: 14 September 2018

Published in: IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/12.67327

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (12)

Connected max cut is polynomial for graphs without the excluded minor \(K_5\backslash e\) ⋮ Finding a maximum minimal separator: graph classes and fixed-parameter tractability ⋮ Computing the largest bond and the maximum connected cut of a graph ⋮ Note on maximal bisection above tight lower bound ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ On the bond polytope ⋮ New approximation results on graph matching and related problems ⋮ \textsc{Max-Cut} parameterized above the Edwards-Erdős bound ⋮ Parliament seating assignment problems ⋮ Mixed-integer programming techniques for the connected max-\(k\)-cut problem ⋮ Approximation algorithms for connected maximum cut and related problems ⋮ New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition

This page was built for publication: Approximation and intractability results for the maximum cut problem and its variants