Approximation algorithms for connected maximum cut and related problems

DOI10.1016/J.TCS.2020.01.016MaRDI QIDQ6828271zbMATH OpenFDO

Authors Mohammad T. Hajiaghayi, Guy Kortsarz, Robert MacDavid, Manish Purohit, Kanthi K. Sarpatwar

Publication date 12 March 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2020.01.016

zbMATH Keywords

approximation algorithmsconnected maximum cutconnected submodular maximization

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cited in

(2)

• Fixed-parameter algorithms for cardinality-constrained graph partitioning problems on sparse graphs
• Fixed-parameter algorithms for cardinality-constrained graph partitioning problems on sparse graphs

This page was built for publication: Approximation algorithms for connected maximum cut and related problems

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