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
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)
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