Approximation algorithms for connected maximum cut and related problems

DOI10.1016/j.tcs.2020.01.016zbMath1445.68166arXiv1507.00648OpenAlexW2949074253WikidataQ126328629 ScholiaQ126328629MaRDI QIDQ2304552

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

Publication date: 12 March 2020

Published in: Theoretical Computer Science, Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1507.00648

zbMATH Keywords

approximation algorithmsconnected maximum cutconnected submodular maximization

Mathematics Subject Classification ID

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

Related Items (10)

Max-Cut Under Graph Constraints ⋮ Computing the largest bond and the maximum connected cut of a graph ⋮ On maximum leaf trees and connections to connected maximum cut problems ⋮ On the bond polytope ⋮ Parameterized Complexity of Multi-Node Hubs ⋮ Mixed-integer programming techniques for the connected max-\(k\)-cut problem ⋮ Approximating graph-constrained max-cut ⋮ Approximating max-cut under graph-MSO constraints ⋮ Approximation algorithms for connected maximum cut and related problems ⋮ Parameterized complexity of multi-node hubs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Connected dominating set. Theory and applications
• Graph minors. III. Planar tree-width
• Treewidth. Computations and approximations
• Approximation algorithms for connected dominating sets
• Primal-dual algorithms for connected facility location problems
• Approximation algorithms for connected maximum cut and related problems
• Efficient graph-based image segmentation
• Deterministic Parameterized Connected Vertex Cover
• Distributed connectivity decomposition
• Submodular Cost Allocation Problem and Applications
• Maximizing Non-monotone Submodular Functions
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• An analysis of approximations for maximizing submodular set functions—I
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Tight Bounds on Vertex Connectivity Under Vertex Sampling
• Approximation and intractability results for the maximum cut problem and its variants
• Submodular Maximization with Cardinality Constraints
• Fast algorithms for maximizing submodular functions
• Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems
• Contraction decomposition in h-minor-free graphs and algorithmic applications
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• A tight bound on approximating arbitrary metrics by tree metrics

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