scientific article; zbMATH DE number 6850401

MaRDI QIDQ4607980zbMATH OpenFDO

Authors Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Vivek Madan

Publication date 15 March 2018

Full work available at URL http://dl.acm.org/citation.cfm?id=3175397

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Approximation algorithms (68W25)

Recommendations

• A tight \(\sqrt{2} \)-approximation for linear 3-cut
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem
• Linear-Time Approximation Algorithms for the Max Cut Problem
• scientific article; zbMATH DE number 1522944
• Approximation the minimum \(k\)-way cut in a graph via minimum 3-way cuts
• scientific article; zbMATH DE number 1256718
• Approximation algorithms for feasible cut and multicut problems
• \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time

Cited in

(5)

• A simple algorithm for the multiway cut problem
• A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP
• An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem
• Minimum violation vertex maps and their applications to cut problems
• A tight \(\sqrt{2} \)-approximation for linear 3-cut

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4607980)